一種基于正六邊形分簇的WSN拓撲控制研究

鄒汪平

（池州職業(yè)技術學院，安徽池州 247000）

低成本的小型嵌入式設備構成的WSN中傳感器由電池供電且節(jié)點運算和通訊能力受其限制。良好的網(wǎng)絡拓撲結構不僅可以提高路由協(xié)議的效率，還可以為時間的同步、目標的定位以及數(shù)據(jù)的融合提供良好的保障，從而延長網(wǎng)絡的生命周期[1]。

1 研究背景

路由算法因WSN的特殊性結構和其管理的邏輯結構的不同而有所不同。從現(xiàn)有的平面路由和層次路來看，前者可均勻分布網(wǎng)絡流量，易于算法的實現(xiàn)，但其由于擴展性問題制約了網(wǎng)絡規(guī)模，而后者因為擴展性好而具有更佳的通信效果。

傳統(tǒng)的LEACH算法是通過更均勻的分簇、更合理的簇首節(jié)點以及中繼節(jié)點的設置來達到增強WSN的通信能力的目的[2]。在此基礎上提出LEACH-H，一種基于正六邊形分簇的WSN拓撲控制研究的算法。該算法旨在基于正六邊形分簇提出一種WSN拓撲控制機制，從而使得分簇均勻，簇首節(jié)點在選擇上更接近簇中心以及剩余能量更多的節(jié)點，轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點能夠獨立與簇首節(jié)點以及簇內(nèi)其他節(jié)點進行遠距離通信，在能量利用率方面得到明顯的改善，網(wǎng)絡的生命周期得到延續(xù)，網(wǎng)絡的吞吐量得到提高。

2 算法改進

使用正六邊形分簇在同一矩形檢測區(qū)域上進行劃分與使用等面積長正方形分簇以及等面積圓形分簇相比較發(fā)現(xiàn)，功率覆蓋上正六邊形分簇與圓形分簇最接近但卻不存在縫隙和重疊，分簇產(chǎn)生的子區(qū)域個數(shù)上正六邊形分簇比正方形分簇要少得多。因此，采用正六邊形分簇，在傳感器節(jié)點傳輸距離確定的前提條件下，可以使用比其他分簇方式更少的傳感器節(jié)點來覆蓋整個監(jiān)測區(qū)域，因此在等面積的正六邊形分簇與正方形分簇相比，簇內(nèi)通訊能耗更低。

考慮到正六邊形分簇區(qū)域內(nèi)節(jié)點分布均勻并且這些節(jié)點的能耗與簇首節(jié)點的距離存在正比例關系，所以正六邊形中心即為簇首節(jié)點的位置，并且這個中心位置設計不斷變化才能夠使得通訊能耗盡可能低。因此，可以將BS節(jié)點（基站節(jié)點）的坐標位置(Xbs,Ybs)修改成(Xbs+offset_x，Ybs+offsset_y)，使得中心在不斷地隨機變化，而offset_x和offset_y是0-正六邊形半徑r之間的隨機數(shù)。這種設置有利于整個網(wǎng)絡的負載均衡。分簇后的區(qū)域中心節(jié)點距離任意簇內(nèi)節(jié)點P(x,y)的距離為dp，則：

由此可知，在傳感器節(jié)點坐標、BS節(jié)點坐標、隨機的偏移量值以及分簇后的子區(qū)域邊長這4個因素確定的情況下就可以得到傳感器節(jié)點隸屬的簇、簇的中心節(jié)點坐標以及該節(jié)點與中心節(jié)點的距離。

在LEACH-H的簇首節(jié)點的選擇機制設計中，若任意節(jié)點i與簇中心相距di，初始能量和生育能量分別為Emax和Eremain，區(qū)域中心與節(jié)點的最大距離為r，則可以得到一般節(jié)點能夠成為簇首節(jié)點的優(yōu)先權Pi是：

簇首節(jié)點的位置和能量由公式中p的取值決定，根據(jù)經(jīng)驗為0.68[3]。

在拓撲結構的建立過程中首先考慮的就是篩選簇首節(jié)點。在此過程中，剩余能量較大且距離分簇的中心節(jié)點較近的節(jié)點都需要優(yōu)先考慮。在篩選時固定的分簇中心致使能夠被篩選為簇首節(jié)點的節(jié)點總是位于分簇中心，這樣單一的生成方式導致整個網(wǎng)絡負載不均衡，因此考慮分簇中心應該在偏移量的作用下不斷發(fā)生改變。由于偏移量在每個簇首節(jié)點的生命周期開始時均隨機生成并通過BS節(jié)點以廣播的方式發(fā)送到分簇內(nèi)的每一個節(jié)點，因此接收到該廣播的偏移量信息后，每個節(jié)點都可以根據(jù)以上描述的機制生成自身所屬分簇以及自身被篩選為簇首節(jié)點和中繼節(jié)點的優(yōu)先權值。利用LEACH-H算法可以在所有網(wǎng)絡節(jié)點計算出自身所屬分簇時向該分簇以廣播形式發(fā)送其被篩選為簇首節(jié)點和中繼節(jié)點的優(yōu)先權值。在分簇子區(qū)域較小的前提條件下，各節(jié)點廣播的能耗也較小，在分簇內(nèi)部那些距離分簇中心越近能量越大的節(jié)點很快就能被確定下來。如果在同一分簇內(nèi)的某節(jié)點接收到其他節(jié)點的廣播后發(fā)現(xiàn)自身的優(yōu)先權值更大，則需要再次以廣播的形式告知簇內(nèi)其他節(jié)點，該步驟一直循環(huán)直到不再有節(jié)點廣播為止，這時簇首節(jié)點被確定，該節(jié)點具備的能量最大，距離分簇中心最近的特點。一旦分簇內(nèi)的簇首節(jié)點生成，分簇內(nèi)的其他節(jié)點便會同時向簇首節(jié)點發(fā)出信息以加入該簇。在分簇內(nèi)的那些距離上與BS節(jié)點越近且剩余能量越大的節(jié)點成為簇內(nèi)中繼節(jié)點的優(yōu)先權限越大，被篩選為中繼節(jié)點的可能性越高。簇首節(jié)點在接收完所有剩余節(jié)點的入簇信息后可以直接判定出能夠篩選出優(yōu)先權限最高的節(jié)點為中繼節(jié)點。一旦簇首節(jié)點與中繼節(jié)點被篩選出來，整個分簇網(wǎng)絡也就進入了相對穩(wěn)定的傳輸階段。

在LEACH-H算法中由于引入了中繼節(jié)點，因此分簇內(nèi)的成員節(jié)點在中繼節(jié)點的作用下以多跳方式將數(shù)據(jù)信息傳遞給BS節(jié)點之后最終到達簇首節(jié)點。該算法與經(jīng)典的LEACH算法相比，由于簇首節(jié)點通信距離更近能耗更低生命周期更長的特點，使得在大范圍WSN中可以更明顯地延長整個網(wǎng)絡的生命周期。

3 仿真及分析

將LEACH-H算法與LEACH算法從網(wǎng)絡生命周期、節(jié)點總能耗和網(wǎng)絡吞吐量3個方面在仿真環(huán)境NS2中進行仿真比較與分析。設計實驗環(huán)境：簇的區(qū)域邊長r設定為200，在400*400的區(qū)域內(nèi)部署400個傳感器節(jié)點，并設置BS節(jié)點的坐標為(65,485)，實驗結果如下：

圖1 生存節(jié)點隨時間變化曲線

圖2 節(jié)點的總能耗隨時間變化曲線

圖3 網(wǎng)絡總吞吐量隨時間變化曲線

實驗結果表明，LEACH-H算法開始產(chǎn)生死亡節(jié)點的時間比LEACH算法更晚，并由于中繼節(jié)點的作用使得簇首節(jié)點的通信負荷得以減輕，與此同時考慮各節(jié)點的剩余能量以均衡整個網(wǎng)絡負載。網(wǎng)絡生命周期上LEACH-H也占有明顯優(yōu)勢。LEACH-H算法下網(wǎng)絡的節(jié)點的總能耗與LEACH算法相比大幅降低，從而使得LEACH-H算法下網(wǎng)絡的吞吐量也得到相應的提高。

4 結語

LEACH-H算法通過使用正六邊形的分簇形式使得分簇更均勻，簇首節(jié)點的生成機制同時得以改進并引入中繼節(jié)點降低通信負荷。在NS2仿真環(huán)境下實驗證明，通過使用LEACH-H算法可充分降低節(jié)點能耗，延長網(wǎng)絡生命周期和提高網(wǎng)絡吞吐量。筆者認為LEACH-H算法不僅提出了一種新的分簇方式，為實際研究工作提供有力的數(shù)據(jù)支持，也為以后的研究工作提供數(shù)據(jù)參考。

[1]劉運杰,金明錄,崔承毅.基于RSSI的無線傳感器網(wǎng)絡修正加權質(zhì)心定位算法[J].傳感技術學報,2010(5):717-721.

[2]朱智輝.網(wǎng)絡化測試中WSN的設計與路由協(xié)議的研究[D].秦皇島:燕山大學,2011.

[3]李德英,陳文萍,霍瑞龍,等.無線傳感器網(wǎng)絡能量高效綜述[J].計算機科學,2008(11):8-12,35.