董兆鑫，華 翔，姜冰清，謝 勤，孫一陽

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

通常無線傳感器網絡(Wireless Sensor Networks,WSNs)中的節(jié)點數(shù)量龐大且資源受限，網絡的壽命長短取決于感知節(jié)點能量消耗的快慢。因此，最大化延長網絡壽命是WSNs的關鍵任務。其中分簇算法是拓撲控制中的一種重要方法[1]。

分簇算法具有適合大規(guī)模網絡環(huán)境，可擴展性好，便于管理及能量利用率高等特點[2]，其中比較經典的算法為Leach算法[3]，但由于其簇頭選擇的隨機性，在網絡拓撲中常出現(xiàn)非均勻分簇的現(xiàn)象，造成輕負載區(qū)節(jié)點能量浪費，從而導致網絡生存時間有限。

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

文中提出一種改進的遺傳聚類拓撲分簇算法，擬結合無線通信信道中的能耗最小模型，選擇對簇心P矩陣編碼，設計針對局部尋優(yōu)的遺傳算子操作與全局最優(yōu)的一步搜索策略，進行網絡均衡劃分，延長網絡壽命。

1 基礎理論

1.1 遺傳搜索

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

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

圖1 遺傳搜索過程

1.2 網絡拓撲最優(yōu)簇模型

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

(1)

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

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

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

(2)

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

假定在面積為A的地域中有N個節(jié)點，分簇為圓形，那么在該面積內的節(jié)點分布密度可表示為ρ=N/A,當傳感器節(jié)點在檢測范圍內均勻分布時，則可得簇內節(jié)點到其對應簇頭的距離均值為

(3)

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

(4)

2 改進的遺傳聚類拓撲分簇算法

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

2.1.1 網絡能耗最優(yōu)模型的構建

文中指導聚類(分簇)的準則是優(yōu)化得到Ku個網絡區(qū)域的最小能耗。結合式(1)和式(2)無線信道傳輸模型與模糊集劃分理論，構造對應的網絡能耗模型為：

(5)

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

由拓撲控制分簇的目標可知，分簇的效果越好，即對應的網絡總能耗就越小，即式(5)的值就越小，而此時劃分的簇對應的適應度應該越大，以體現(xiàn)優(yōu)化分簇過程中可行解接近最優(yōu)解的優(yōu)良水平。因此結合對應的最優(yōu)網絡能耗模型來構造適應度函數(shù)，其表達式為

(6)

2.1.2P矩陣編碼簇心

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

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

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

2.1.3 自適應遺傳算子的構造

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

1) 選擇算子

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

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

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

2) 交叉算子

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

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

3) 變異算子

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

構造下式指導變異位的選擇以進行變異操作。

2.1.4 一步迭代策略

文中基于上述遺傳操作的迭代中提出一步迭代策略，以保證基站進行網絡分簇時快速收斂的實時性要求。

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

(7)

(8)

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

2.2 實驗仿真與分析

節(jié)點分布在監(jiān)測區(qū)域，節(jié)點通過自身定位技術將位置坐標傳給基站，基站利用遺傳聚類算法對網絡節(jié)點進行分簇，與最優(yōu)聚類中心距離最近的節(jié)點被選為簇頭，劃分拓撲結構。簇內成員不變，設定簇頭當選時間而后考察節(jié)點能耗情況，以剩余能量最多為準則選取簇頭，再次由基站重新對網絡進行分簇。

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

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

表1 實驗仿真參數(shù)

在對該WSN網絡進行遺傳搜索分簇時，需確定最優(yōu)簇數(shù)。取對應參數(shù)N=100，A=100 m×100 m，εfs=10 pJ，εmp=0.001 3 pJ，87

2.2.2 拓撲劃分仿真

拓撲劃分實驗結果如圖2所示，全網劃分簇數(shù)為5，且每次實驗結果中均能保持簇內節(jié)點數(shù)位20個左右，沒有出現(xiàn)簇頭聚集或缺失，同樣無分簇結果陷入局部最優(yōu)解的情況，可以實現(xiàn)網絡拓撲的均勻劃分。星形表示分簇結果中的聚類中心。

圖2 改進的遺傳聚類分簇結果

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

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

圖3 節(jié)點聚類準確率對比

圖4為網絡拓撲分簇速度對比，從圖4可以看出，標準遺傳算法的收斂代數(shù)約為88，F(xiàn)KM算法的收斂代數(shù)為61，而文中算法的收斂速度為32，相比標準遺傳算法速度提高約63%，相比FKM速度提高約47%。

圖4 算法收斂曲線對比

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

2.2.3 網絡能耗仿真實驗

網絡能耗仿真實驗以能耗效果較好的REDDC算法[13]和粗糙C-Leach算法[14]作為對比，在每次實驗簇頭選舉進行到第300輪為固定時間節(jié)點測算，測算每種算法劃分5個區(qū)域內的負載的標準差，進而得出本次實驗整個網絡的區(qū)域負載標準差極差值，在100次實驗中觀察每種算法均衡趨勢。

圖5為REDDC算法、粗糙C-Leach算法以及文中算法的簇內負載標準差的極差對比，由圖5可以看出,REDDC算法由于簇頭隨機分布不均而引發(fā)的“能量熱點”問題，導致極差為3.5，簇間負載波動較大；粗糙C-Leach分簇較之有明顯改善，簇間極差均值為1.1，但依舊因為有陷入局部最優(yōu)解現(xiàn)象導致網絡負載不穩(wěn)定；文中算法在每次實驗中劃分網絡負載均衡，負載極差值0.6。因此,文中算法對避免簇間負載不均衡的問題具有明顯效果，可以進行延長網絡生存時間實驗。

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

圖5 簇間負載極差對比

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

統(tǒng)計所有節(jié)點全部死亡時，網絡運行的極限時間對比，其中文中算法延長網絡壽命的效果是REDDC算法的1.5倍，是粗糙C-Leach算法的1.1倍。

實際中，常以網絡開始運行至50%節(jié)點死亡的時長為WSNs的生命周期，從這個角度上考慮，文中改進算法的網絡延長效果比REDDC算法提高了約84%，比粗糙C-Leach的分簇效果提高了約27%，說明隨著網絡的持續(xù)運行，文中改進的遺傳聚類拓撲分簇算法對網絡周期的延長效果逐漸加強，時間延長效果明顯。

3 結 論

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