一種改進(jìn)的遺傳聚類拓?fù)浞执厮惴?/h1>

2019-02-13 01:33:06董兆鑫姜冰清孫一陽(yáng)

西安工業(yè)大學(xué)學(xué)報(bào)訂閱 2019年1期 收藏

關(guān)鍵詞：算子遺傳算法基站

董兆鑫，華 翔，姜冰清，謝 勤，孫一陽(yáng)

(西安工業(yè)大學(xué) 電子信息工程學(xué)院，西安 710021)

通常無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)中的節(jié)點(diǎn)數(shù)量龐大且資源受限，網(wǎng)絡(luò)的壽命長(zhǎng)短取決于感知節(jié)點(diǎn)能量消耗的快慢。因此，最大化延長(zhǎng)網(wǎng)絡(luò)壽命是WSNs的關(guān)鍵任務(wù)。其中分簇算法是拓?fù)淇刂浦械囊环N重要方法[1]。

分簇算法具有適合大規(guī)模網(wǎng)絡(luò)環(huán)境，可擴(kuò)展性好，便于管理及能量利用率高等特點(diǎn)[2]，其中比較經(jīng)典的算法為L(zhǎng)each算法[3]，但由于其簇頭選擇的隨機(jī)性，在網(wǎng)絡(luò)拓?fù)渲谐３霈F(xiàn)非均勻分簇的現(xiàn)象，造成輕負(fù)載區(qū)節(jié)點(diǎn)能量浪費(fèi)，從而導(dǎo)致網(wǎng)絡(luò)生存時(shí)間有限。

聚類算法是根據(jù)事物的特征對(duì)其進(jìn)行分析分類，引入該思想進(jìn)行網(wǎng)絡(luò)簇頭分配可以有效地平衡簇間的能量消耗。其中文獻(xiàn)[4]利用模糊K均值聚類算法(Fuzzy K-Means,FKM) 基本實(shí)現(xiàn)了對(duì)全網(wǎng)均勻分簇，但該方法存在對(duì)原型初始值敏感，容易出現(xiàn)局部最優(yōu)劃分的情況。文獻(xiàn)[5]在FKM的基礎(chǔ)上，結(jié)合譜聚類，減小了網(wǎng)絡(luò)拓?fù)渲g的網(wǎng)絡(luò)時(shí)延，進(jìn)一步提高簇頭劃分的準(zhǔn)確性，但是，該算法也保留了FKM容易陷入局部最優(yōu)解的特點(diǎn)。文獻(xiàn)[6]針對(duì)FKM分簇中對(duì)初始值敏感的問題，引入遺傳算法(Genetic Algorithm,GA)搜索全局最優(yōu)簇，但同時(shí)也引入了數(shù)據(jù)計(jì)算量隨著節(jié)點(diǎn)規(guī)模呈平方遞增的特點(diǎn)，導(dǎo)致其收斂速度較慢而引發(fā)的能耗時(shí)延不均的問題。

文中提出一種改進(jìn)的遺傳聚類拓?fù)浞执厮惴?，擬結(jié)合無線通信信道中的能耗最小模型，選擇對(duì)簇心P矩陣編碼，設(shè)計(jì)針對(duì)局部尋優(yōu)的遺傳算子操作與全局最優(yōu)的一步搜索策略，進(jìn)行網(wǎng)絡(luò)均衡劃分，延長(zhǎng)網(wǎng)絡(luò)壽命。

1 基礎(chǔ)理論

1.1 遺傳搜索

遺傳搜索是建立在達(dá)爾文自然選擇學(xué)說和孟德爾遺傳規(guī)律基礎(chǔ)之上的隨機(jī)搜索算法[7]，搜索過程如圖1所示，提出了一種處理多元問題的簡(jiǎn)明框架，通過構(gòu)造遺傳算子進(jìn)行針對(duì)性尋找優(yōu)化問題的解。

算法執(zhí)行步驟為：① 選擇合適的編碼方式，將待優(yōu)化個(gè)體編碼成解空間中的基因串結(jié)構(gòu)；② 構(gòu)造評(píng)估函數(shù)以衡量目標(biāo)對(duì)象的適應(yīng)值；③ 構(gòu)建遺傳策略，設(shè)定初始化空間個(gè)體數(shù)、交叉率、變異率、選擇算子、交叉算子以及變異算子的構(gòu)造和進(jìn)化終止條件；④ 按照編碼方式初始化群體并得出種群個(gè)體的適應(yīng)度值；⑤ 根據(jù)遺傳策略，執(zhí)行遺傳算子選擇進(jìn)化出下一代種群；⑥ 判斷迭代終止準(zhǔn)則，滿足則劃分搜索結(jié)果，否則返回上一步再次進(jìn)化新群體。

圖1 遺傳搜索過程

1.2 網(wǎng)絡(luò)拓?fù)渥顑?yōu)簇模型

文獻(xiàn)[8]根據(jù)節(jié)點(diǎn)發(fā)送與接收間的距離將信道劃分為多徑衰落信道和自由空間傳播信道，并給出其發(fā)送1 bit信息所需的能量公式為

(1)

式中:Eelec為發(fā)送電路和接收電路所需的能量；εfs和εmp分別為自由空間傳播模型和多徑衰落模型中放大器所耗能量；L和D分別為節(jié)點(diǎn)到匯聚點(diǎn)的間距和匯聚點(diǎn)到傳輸基站的間距。

WSN被劃分成K簇，那么確定最優(yōu)簇?cái)?shù)K即可使得網(wǎng)絡(luò)信息傳輸?shù)目偰芎倪_(dá)到最低，這里給出每1 bit信息從節(jié)點(diǎn)經(jīng)過簇頭傳送至傳輸基站總能耗E(K)為

E(K)=K×((N/K-1)×efs+emp)

(2)

式中：efs為1 bit信息在節(jié)點(diǎn)間以自由空間傳播模型傳遞給簇頭所消耗的能量；emp為簇頭將1 bit信息傳遞至傳輸基站的能耗。

假定在面積為A的地域中有N個(gè)節(jié)點(diǎn)，分簇為圓形，那么在該面積內(nèi)的節(jié)點(diǎn)分布密度可表示為ρ=N/A,當(dāng)傳感器節(jié)點(diǎn)在檢測(cè)范圍內(nèi)均勻分布時(shí)，則可得簇內(nèi)節(jié)點(diǎn)到其對(duì)應(yīng)簇頭的距離均值為

(3)

要取k變化時(shí)的最優(yōu)簇頭數(shù)目，聯(lián)合式(1)～(3)并對(duì)k求偏導(dǎo)得：

(4)

2 改進(jìn)的遺傳聚類拓?fù)浞执厮惴?/h2>

2.1 算法具體實(shí)現(xiàn)

2.1.1 網(wǎng)絡(luò)能耗最優(yōu)模型的構(gòu)建

文中指導(dǎo)聚類(分簇)的準(zhǔn)則是優(yōu)化得到Ku個(gè)網(wǎng)絡(luò)區(qū)域的最小能耗。結(jié)合式(1)和式(2)無線信道傳輸模型與模糊集劃分理論，構(gòu)造對(duì)應(yīng)的網(wǎng)絡(luò)能耗模型為：

(5)

其中，w=[wij]k*n為劃分矩陣;p=(p1,p2,…,pk)T∈Rkm為k個(gè)聚類的原型模式;Eji為節(jié)點(diǎn)j發(fā)送1 bit信息到簇頭i的能量；Eis為簇頭i把1 bit信息傳遞至匯聚基站的能耗。

由拓?fù)淇刂品执氐哪繕?biāo)可知，分簇的效果越好，即對(duì)應(yīng)的網(wǎng)絡(luò)總能耗就越小，即式(5)的值就越小，而此時(shí)劃分的簇對(duì)應(yīng)的適應(yīng)度應(yīng)該越大，以體現(xiàn)優(yōu)化分簇過程中可行解接近最優(yōu)解的優(yōu)良水平。因此結(jié)合對(duì)應(yīng)的最優(yōu)網(wǎng)絡(luò)能耗模型來構(gòu)造適應(yīng)度函數(shù)，其表達(dá)式為

(6)

2.1.2P矩陣編碼簇心

為了避免了搜索空間隨數(shù)據(jù)量呈平方遞增的關(guān)系[9]，文中采用對(duì)簇心P矩陣編碼以縮小算法的搜索空間，加快收斂速度。由式(4)得到聚類的類別數(shù)K后，即可按照遺傳策略進(jìn)行最優(yōu)分簇。將K組表示簇心的特征參數(shù)相連起來，根據(jù)各自參數(shù)的取值范圍，將其量化值(用二進(jìn)制串表示)編碼成基因串。

I=Ec{p1,p2,…pk}=

此時(shí)搜索空間只與樣本形參m和類別數(shù)K有關(guān)，同時(shí)采用Gray碼對(duì)上述特征參數(shù)進(jìn)行編碼，以避免十進(jìn)制極小的數(shù)值變化卻引起多位比特位發(fā)生變化。

2.1.3 自適應(yīng)遺傳算子的構(gòu)造

文中通對(duì)各級(jí)算子進(jìn)行自適應(yīng)動(dòng)態(tài)操作概率設(shè)計(jì)，使其依次完成選擇算子、交叉算子和變異算子的逐層分級(jí)操作，提高最優(yōu)解搜索過程中的定向指導(dǎo)效率。

1) 選擇算子

為了確保穩(wěn)定有效的選擇壓力，又能保持群體多樣性，防止迭代早熟收斂[10]，文中通過設(shè)計(jì)依據(jù)待求解的優(yōu)良程度得到對(duì)應(yīng)被選擇的概率，以提高得到最優(yōu)解的可能性。

選擇操作以排序選擇法動(dòng)態(tài)分配給待求解被選擇概率，再以輪盤賭法隨機(jī)進(jìn)行個(gè)體選種。這里給出選擇概率函數(shù)為

式中：N為樣本數(shù)量；i為排序排名。

2) 交叉算子

文中選擇單點(diǎn)交叉結(jié)合多段重組的方式對(duì)父代個(gè)體中優(yōu)良基因特性進(jìn)行隨機(jī)交換重組，執(zhí)行最優(yōu)搜索理論中的局部尋優(yōu)。

構(gòu)造下式自適應(yīng)交叉率以提高獲取優(yōu)良基因的概率。

3) 變異算子

文中以動(dòng)態(tài)變化的變異率指導(dǎo)群體個(gè)體的基因串中變異位的選擇，可以增加不同可行解的搜索范圍的多樣性，提高局部尋優(yōu)的搜索能力。

構(gòu)造下式指導(dǎo)變異位的選擇以進(jìn)行變異操作。

2.1.4 一步迭代策略

文中基于上述遺傳操作的迭代中提出一步迭代策略，以保證基站進(jìn)行網(wǎng)絡(luò)分簇時(shí)快速收斂的實(shí)時(shí)性要求。

利用模糊理論計(jì)算提高遺傳搜索簇心參數(shù)的精確程度，具體實(shí)現(xiàn)通過在每次遺傳搜索迭代中執(zhí)行以下兩步操作。

(7)

(8)

式中：i∈[1,Ku]；j∈[1,n]，n為樣本數(shù)量。在由式(8)更新得到了新的簇心后，再將其編碼成新的群體個(gè)體基因串，重新執(zhí)行新一代遺傳操作，直至算法收斂到最優(yōu)分簇。

2.2 實(shí)驗(yàn)仿真與分析

節(jié)點(diǎn)分布在監(jiān)測(cè)區(qū)域，節(jié)點(diǎn)通過自身定位技術(shù)將位置坐標(biāo)傳給基站，基站利用遺傳聚類算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分簇，與最優(yōu)聚類中心距離最近的節(jié)點(diǎn)被選為簇頭，劃分拓?fù)浣Y(jié)構(gòu)。簇內(nèi)成員不變，設(shè)定簇頭當(dāng)選時(shí)間而后考察節(jié)點(diǎn)能耗情況，以剩余能量最多為準(zhǔn)則選取簇頭，再次由基站重新對(duì)網(wǎng)絡(luò)進(jìn)行分簇。

2.2.1 最優(yōu)簇頭數(shù)選擇

將100個(gè)節(jié)點(diǎn)任意部署于100 m×100 m觀測(cè)地域，基站的坐標(biāo)為(115，50)，觀測(cè)節(jié)點(diǎn)的起始能量均為0.5 J，同時(shí)假定目標(biāo)間的通信是對(duì)稱且無信道碰撞。具體參數(shù)值設(shè)置參考文獻(xiàn)[11]，見表1。

表1 實(shí)驗(yàn)仿真參數(shù)

在對(duì)該WSN網(wǎng)絡(luò)進(jìn)行遺傳搜索分簇時(shí)，需確定最優(yōu)簇?cái)?shù)。取對(duì)應(yīng)參數(shù)N=100，A=100 m×100 m，εfs=10 pJ，εmp=0.001 3 pJ，87

2.2.2 拓?fù)鋭澐址抡?/p>

拓?fù)鋭澐謱?shí)驗(yàn)結(jié)果如圖2所示，全網(wǎng)劃分簇?cái)?shù)為5，且每次實(shí)驗(yàn)結(jié)果中均能保持簇內(nèi)節(jié)點(diǎn)數(shù)位20個(gè)左右，沒有出現(xiàn)簇頭聚集或缺失，同樣無分簇結(jié)果陷入局部最優(yōu)解的情況，可以實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涞木鶆騽澐?。星形表示分簇結(jié)果中的聚類中心。

圖2 改進(jìn)的遺傳聚類分簇結(jié)果

由于標(biāo)準(zhǔn)遺傳聚類算法是源自FKM聚類而發(fā)展來的[13]，故實(shí)驗(yàn)以FKM算法和標(biāo)準(zhǔn)遺傳算法作為文中算法聚類準(zhǔn)確性和算法收斂速度對(duì)比算法。

圖3為節(jié)點(diǎn)分簇的準(zhǔn)確率對(duì)比，可以看出文中算法每次分簇的準(zhǔn)確率均在99%左右，而標(biāo)準(zhǔn)遺傳算法的分類準(zhǔn)確率維持在84%，而FKM聚類起伏波動(dòng)大，容易陷入局部最優(yōu)解。文中改進(jìn)的遺傳算法通過一步迭代策略進(jìn)行模糊計(jì)算，實(shí)現(xiàn)對(duì)標(biāo)準(zhǔn)遺傳算法聚類精確性的提高，完成對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)分簇的準(zhǔn)確劃分。

圖3 節(jié)點(diǎn)聚類準(zhǔn)確率對(duì)比

圖4為網(wǎng)絡(luò)拓?fù)浞执厮俣葘?duì)比，從圖4可以看出，標(biāo)準(zhǔn)遺傳算法的收斂代數(shù)約為88，F(xiàn)KM算法的收斂代數(shù)為61，而文中算法的收斂速度為32，相比標(biāo)準(zhǔn)遺傳算法速度提高約63%，相比FKM速度提高約47%。

圖4 算法收斂曲線對(duì)比

由于標(biāo)準(zhǔn)遺傳算法相比FKM具有更加復(fù)雜的計(jì)算度，收斂速度相比較慢，而改進(jìn)的遺傳算法應(yīng)用改進(jìn)的自適應(yīng)遺傳算子動(dòng)態(tài)地指導(dǎo)最優(yōu)解搜索方向，使得其搜索效率明顯提高。同時(shí)在收斂質(zhì)量上結(jié)合一步搜索策略精確搜索結(jié)果，文中算法的個(gè)體適應(yīng)度值最高，達(dá)到1.82左右。

2.2.3 網(wǎng)絡(luò)能耗仿真實(shí)驗(yàn)

網(wǎng)絡(luò)能耗仿真實(shí)驗(yàn)以能耗效果較好的REDDC算法[13]和粗糙C-Leach算法[14]作為對(duì)比，在每次實(shí)驗(yàn)簇頭選舉進(jìn)行到第300輪為固定時(shí)間節(jié)點(diǎn)測(cè)算，測(cè)算每種算法劃分5個(gè)區(qū)域內(nèi)的負(fù)載的標(biāo)準(zhǔn)差，進(jìn)而得出本次實(shí)驗(yàn)整個(gè)網(wǎng)絡(luò)的區(qū)域負(fù)載標(biāo)準(zhǔn)差極差值，在100次實(shí)驗(yàn)中觀察每種算法均衡趨勢(shì)。

圖5為REDDC算法、粗糙C-Leach算法以及文中算法的簇內(nèi)負(fù)載標(biāo)準(zhǔn)差的極差對(duì)比，由圖5可以看出,REDDC算法由于簇頭隨機(jī)分布不均而引發(fā)的“能量熱點(diǎn)”問題，導(dǎo)致極差為3.5，簇間負(fù)載波動(dòng)較大；粗糙C-Leach分簇較之有明顯改善，簇間極差均值為1.1，但依舊因?yàn)橛邢萑刖植孔顑?yōu)解現(xiàn)象導(dǎo)致網(wǎng)絡(luò)負(fù)載不穩(wěn)定；文中算法在每次實(shí)驗(yàn)中劃分網(wǎng)絡(luò)負(fù)載均衡，負(fù)載極差值0.6。因此,文中算法對(duì)避免簇間負(fù)載不均衡的問題具有明顯效果，可以進(jìn)行延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間實(shí)驗(yàn)。

在網(wǎng)絡(luò)負(fù)載耗能的基礎(chǔ)上比較整個(gè)網(wǎng)絡(luò)壽命，如表2統(tǒng)計(jì)所得，若以第一個(gè)節(jié)點(diǎn)死亡時(shí)間定義網(wǎng)絡(luò)生命周期，那么REDDC算法網(wǎng)絡(luò)可以運(yùn)行304輪，對(duì)應(yīng)的粗糙C-Leach分簇算法使得同一個(gè)網(wǎng)絡(luò)多延長(zhǎng)了324輪，文中算法比粗糙C-Leach算法多59輪，說明在網(wǎng)絡(luò)衰退初始階段，文中算法有網(wǎng)絡(luò)生命延長(zhǎng)效果，但效果不顯著。

圖5 簇間負(fù)載極差對(duì)比

實(shí)驗(yàn)算法第一節(jié)點(diǎn)死亡50%節(jié)點(diǎn)死亡節(jié)點(diǎn)全部死亡REDDC3047031 050粗糙CLeach6281 0151 440文中算法6871 2931 600

統(tǒng)計(jì)所有節(jié)點(diǎn)全部死亡時(shí)，網(wǎng)絡(luò)運(yùn)行的極限時(shí)間對(duì)比，其中文中算法延長(zhǎng)網(wǎng)絡(luò)壽命的效果是REDDC算法的1.5倍，是粗糙C-Leach算法的1.1倍。

實(shí)際中，常以網(wǎng)絡(luò)開始運(yùn)行至50%節(jié)點(diǎn)死亡的時(shí)長(zhǎng)為WSNs的生命周期，從這個(gè)角度上考慮，文中改進(jìn)算法的網(wǎng)絡(luò)延長(zhǎng)效果比REDDC算法提高了約84%，比粗糙C-Leach的分簇效果提高了約27%，說明隨著網(wǎng)絡(luò)的持續(xù)運(yùn)行，文中改進(jìn)的遺傳聚類拓?fù)浞执厮惴▽?duì)網(wǎng)絡(luò)周期的延長(zhǎng)效果逐漸加強(qiáng)，時(shí)間延長(zhǎng)效果明顯。

3 結(jié) 論

文中提出的一種改進(jìn)的遺傳聚類拓?fù)浞执厮闶窃跇?biāo)準(zhǔn)遺傳搜索的基礎(chǔ)上，依靠P矩陣編碼縮小搜索空間，采取動(dòng)態(tài)遺傳算子和一步迭代策略加強(qiáng)在局部尋優(yōu)的搜索效率及全局最優(yōu)的精確能力，定向指導(dǎo)搜索方向，達(dá)到了在標(biāo)準(zhǔn)算法的基礎(chǔ)上提高約47%的搜索速度，同時(shí)最高可延長(zhǎng)84%的網(wǎng)絡(luò)生存周期的效果。但是文中算法同樣存在操作復(fù)雜和節(jié)點(diǎn)平面化的不足，因此未來的研究工作將在降低該算法復(fù)雜度的基礎(chǔ)上規(guī)劃實(shí)際節(jié)點(diǎn)間信息傳遞路由，實(shí)現(xiàn)網(wǎng)絡(luò)能耗的降低及應(yīng)用。

猜你喜歡

算子遺傳算法基站

擬微分算子在Hp(ω)上的有界性

數(shù)學(xué)物理學(xué)報(bào)(2021年2期)2021-06-09 08:54:26

各向異性次Laplace算子和擬p-次Laplace算子的Picone恒等式及其應(yīng)用

應(yīng)用數(shù)學(xué)(2020年2期)2020-06-24 06:02:44

一類Markov模算子半群與相應(yīng)的算子值Dirichlet型刻畫

數(shù)學(xué)年刊A輯(中文版)(2018年2期)2019-01-08 01:59:54

基于自適應(yīng)遺傳算法的CSAMT一維反演

石油地球物理勘探(2017年2期)2017-11-23 06:02:04

一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用

中央民族大學(xué)學(xué)報(bào)(自然科學(xué)版)(2017年1期)2017-06-11 07:13:32

可惡的“偽基站”

探索科學(xué)(2017年4期)2017-05-04 04:09:47

基于遺傳算法和LS-SVM的財(cái)務(wù)危機(jī)預(yù)測(cè)

統(tǒng)計(jì)與決策(2017年2期)2017-03-20 15:25:24

Roper-Suffridge延拓算子與Loewner鏈

數(shù)學(xué)物理學(xué)報(bào)(2016年3期)2016-12-01 05:36:27

基于GSM基站ID的高速公路路徑識(shí)別系統(tǒng)

中國(guó)交通信息化(2016年8期)2016-06-06 03:56:25

基于改進(jìn)的遺傳算法的模糊聚類算法

智能系統(tǒng)學(xué)報(bào)(2015年4期)2015-12-27 09:38:39

西安工業(yè)大學(xué)學(xué)報(bào)2019年1期

西安工業(yè)大學(xué)學(xué)報(bào)的其它文章

本刊榮獲“第五屆陜西省科技期刊優(yōu)秀期刊”

本刊榮獲“2018年度中國(guó)高校編輯出版質(zhì)量?jī)?yōu)秀科技期刊”

本刊繼續(xù)被認(rèn)定為“中國(guó)科技核心期刊”

董事網(wǎng)絡(luò)和產(chǎn)品市場(chǎng)競(jìng)爭(zhēng)與信息披露質(zhì)量

陜西省生態(tài)文明建設(shè)效率評(píng)價(jià)研究

AlMo0.5NbTa0.5TiZr難熔高熵合金微觀組織及力學(xué)性能研究