WSN中簇首角色自適應能量樹鏈算法

關 昕，王 杰，陶志勇

1.遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105

2.遼寧工程技術大學 研究生學院，遼寧 葫蘆島 125105

WSN中簇首角色自適應能量樹鏈算法

關 昕1，王 杰2，陶志勇1

1.遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105

2.遼寧工程技術大學 研究生學院，遼寧 葫蘆島 125105

無線傳感器網絡（Wireless Sensor Network，WSN）中無線通信單元是消耗能量主要單元[1]。傳感器節點能量有限且無法補充。網絡拓撲結構的合理性影響高層通信協議的執行和網絡運行能耗，且傳輸比運算處理一個比特的能耗大很多倍[1]。從節點參與通信的拓撲和方式，可以將WSN路由協議分為平面路由協議和分簇路由協議。典型的平面路由協議有SPIN[2]、Directed Diffusion[3]、Rumor[4]等。分簇更符合傳感器網絡的特性，經典的有LEACH[5]、HEED[6]、PEGASIS[7]、TEEN[8]、DWEHC[9]、ACE[10]、FLOC[11]等。

1 相關路由協議

文獻[12]提出分層鏈樹的路由協議，根據節點與sink的距離為圓心劃分環狀層次區域，并形成多跳并行的有向鏈連接到主鏈上。但忽視了不同層的節點能量的差異，鏈路具有不穩定性。文獻[13]提出了一種簇頭成鏈算法LEACH-P。能有效地延長網絡生存周期，但是簇內仍然是一跳通信，而且簇首的分布不受控制，沒有避免簇內和簇首間長鏈的消耗。文獻[14]基于最小生成樹多跳通信，將節點的度作為競爭因子，引入非均勻分簇，簇的大小取決于簇頭節點到sink節點的距離。但最小生成樹沒有考慮節點的剩余能量。文獻[15]在PEGASIS的基礎上引入距離門限避免相鄰節點間產生長鏈。但固定的距離門限使成鏈喪失了自適應性。且每個節點成鏈延遲較大。文獻[16-19]也提出了各自針對LEACH或PEGASIS的改進。

2 約束簇位置的能量樹成鏈算法

本文針對以上協議提出了簇首角色自適應能量樹成鏈算法（Energy-tree Chain algorithm of Role-adaptive Cluster head，ECRC）。該算法通過設置參考點控制前期簇頭的分布，節點根據到最近簇首距離的自適應探測范圍匯聚于“大能量節點”，形成能量從根到葉依次降低的“能量樹”，能量樹根節點成單鏈由鏈首向sink節點發送數據，并為低能量的能量樹根節點設置選舉閾值和替換方案。

本文算法分成四個階段：簇頭選舉階段，能量樹建立階段，能量樹根節點成鏈階段，數據傳輸階段。所有的節點根據接收的信號強度指示（Received Signal Strength Indication，RSSI）可以獲知自己的位置信息，并具有一定數目的可調功率，根據接收者的距離遠近，自動地調節其發送功率。

2.1 算法中的變量參數設定

（1）pi(n)為每個節點自身產生的隨機數。節點每輪產生的0～1之間的隨機數，用來和T1(n)或T2(n)比較，確定是否符合選簇首的條件。

（2）T1(n)為前T輪選簇首的閾值。

（3）Q為成簇的間隔輪數。是輪數r的函數，在仿真環節具體設置。

（4）T為對簇首的位置和個數的輪數限制。開始時簇首個數為5且受到參考節點的限制。T輪后簇首的個數可以小于5，并且由選簇首的閾值T2(n)判斷隨機選出的節點是否擔任簇首。基于實驗觀測首個死亡節點出現的輪數的期望來進行設置。

（5）T2(n)為T輪后選簇首的參數。

LEACH一大輪后G置零忽略了本輪中能量消耗的差異，這里不再設置“G置零”，而是改為用能量閾值M來判斷是否讓其擔任簇首。

（6）M為能量閾值。能量閾值為能量樹根節點完成一輪通信所需的最小能量。能量樹根節點（簇首或大能量節點）完成本輪通信所需的能量值閾值M為：廣播自身剩余能量的能耗+接受廣播信息的能耗+接收普通節點數據的能耗+數據融合的能耗+轉發單鏈上和自身融合后的數據給其他能量樹根節點的能耗。

該值在每次實驗階段的前T輪通過對每個能量樹根節點的以上列出部分的能耗求平均值得出。在T輪之后的選簇公式和能量閾值中應用。屬于反饋值，具有對每次實驗的參數和場景變化的自適應性。

（7）S為能距因子。能距因子的計算公式S=Eleft/ dtosink，其中dtosink為能量樹根節點到sink節點的距離，Eleft為能量樹根節點剩余的能量。

（8）Ci為前T輪共用的簇首標記位。

2.2 參考點設置

本文首次提出了設置參考點來約束簇首位置。而且算法中節點到最近的簇首的距離決定了其加入能量樹的探測范圍，100個節點的最優簇首數目在5個左右[16]，故前期簇首數目設置為5。前期單個能量樹結構分布的區域較小。后期節點死亡增多則對應的簇首數目應該減少，簇首位置也不再限制，簇首和能量樹根節點分布就變靈活，實現對節點普遍低剩余能量情況下的路由的合理構建。

在100×100的分布區域內，前期先設置5個參考點（圖1～3中的菱形），坐標分別為（25，25），（25，75），（50，50），（75，25），（75，75）。在前T輪中簇首在距離參考點L1～L5范圍內的節點中選取。

如圖1和圖2，參考節點1～4的 L1～L4設置為25。為了避免長距離傳輸設置中間參考節點：L5為25。中間區域與周圍有4個重疊區域，為不讓中間區域節點能量因選簇過早耗盡，擴大共有區域使中間區域的可選節點變多并通過對節點設置公共的簇首標記位Ci避免重復選簇。

如圖3，實際選擇簇首的區域完全由每個小正方形區域（50×50）的內接圓決定，避開了簇首在邊緣地區的不利情況。

圖1 L1～L4

圖2 L5

圖3 100×100

增設參考點可以將多個（100×100）區域拼接在一起（如200×100）。根據實際監測區域面積對參考點個數進行設置。

2.3 簇頭選舉階段

（1）第一輪先基于參考點選出5個簇首，簇首成單鏈將信息匯聚到sink節點。第一輪結束后，節點能量將產生差異。

（2）從第二輪開始計數，每隔Q輪成簇。設置一個標記Q_round，值隨著輪數r的增加而減小。

（3）用成簇算法（此時參數T1(n)）產生在離參考點L1～L5距離內的5個簇首。

算法流程圖如圖4所示。

圖4 算法流程圖

與文獻[13-14]相比，本文算法設置了前期簇頭的個數和選舉范圍以均衡能耗。而且sink節點沒有輔助選擇簇首分布，是分布式計算，更好地適應WSN分布式的特性。

2.4 能量樹建立階段

本文首次提出使節點探測和發送的距離為每個節點到最近簇首的距離以適應最近的轉發點形成合理的多跳路由樹。該階段的目標是在全網中建立各自獨立且均勻分布的能量樹結構。

（1）簇首在全網廣播自己當選簇首的信號（Advertisement Message，ADV）。

（2）全網內所有節點收到廣播后分別計算到最近的簇首的距離設為D(r，i)（即是第r輪第i個節點到最近簇首的距離），所有節點（包括簇首）分別以自己的D(r，i)為半徑向附近廣播自己的當前剩余能量Eleft，并附帶自己的ID號。

（3）所有節點將收到的附近節點ID和簇首的能量信息以能量從大到小的有序表方式保存。

（4）節點比較有序表后將會把信息轉發給在其D(r，i)距離內，能量最大的節點（可以是大能量節點或是簇首節點），形成一些各自分離的能量樹。如果節點周圍的D(r，i)距離的節點中剩余能量最大的非簇首節點和最近簇首的節點能量相同，則優先發送給非簇首節點。

（5）簇首也對周圍的節點能量進行比較，并轉發收到的信息給周圍的大能量節點。除非自身的能量在附近節點中最大，此時簇首自身將作為能量樹的根節點。

（6）能量樹根節點（可以是大能量的普通節點或大能量的簇首節點）將收到的信息數據融合后準備進行轉發。

與文獻[12-13]相比，本文算法能量樹的建立沒有以節點到sink的距離為判斷依據，而是以自身的檢測范圍內的節點能量排序來建立。在每個區域內實現能量地理位置分布的適應性，并且避免了長鏈。

本文首次讓簇首同時具有被約束的位置特性和隨機選取的概率特性。并由這兩種特性將簇首擔任收集簇內信息和連接劃分區域以傳遞能量樹根節點信息的雙重角色。并且此處的“簇內”已不再是單獨依據最近距離來判斷，而是在與大能量節點包括距離和能量的競爭中來獲取歸屬自己的節點。此時連接簇首的節點的情況是：離簇首較近，且范圍內無比簇首能量更大。因為在離簇首遠距離的范圍中大能量節點很可能出現。從而避免了到簇首的長距離傳輸，分擔了簇首轉發遠距離節點信息的任務，同時簇首因為其位置人為設定的均勻性也能承擔起轉發能量樹根節點信息的功能（參考點的均勻性保障了簇首的均勻性，而簇首作為探測距離的端節點的均勻性又保障了能量樹分布的均勻性）。同時簇首具有角色自適應性：當簇首能量偏低時其自身吸引普通節點的競爭力就下降，甚至會不接收其他節點的信息而成為實際上的普通節點，這樣就及時保護了節點和路由的有效性，而且不用任何的提前設定，都是節點根據探測與節點競爭的動態判斷。這更加符合WSN的動態的分布式計算的特點，同時低能量節點仍然可以通過樹狀拓撲的層次轉移，用多跳和子節點的方式轉發信息將能耗轉移給附近的大能量節點，實現基于節點互助動態能耗平衡。

2.5 能量樹根節點成鏈階段

本文首次將簇，樹，鏈三種結構有效地結合在一起，提出能量樹成鏈的方法，與簇首或簇內最小生成樹成鏈有很大不同，主要體現在能量和距離的適應性上。該階段的目標是把全網中已經建立好的各自獨立能量樹結構的根節點用單鏈串聯起來。

（2）由最遠的節點開始，每個能量樹根節點根據貪婪算法找到離自己最近的向sink節點靠攏的下一個能量樹根節點。

（3）由離sink最遠到最后一個節點，用貪婪算法一跳跳地連接起來。

（4）單鏈形成后，由sink節點在能量樹根節點（大能量節點和簇首節點）中選出一個到sink節點能距因子S(r，i)最大的節點，作為鏈首節點。S(r，i)表示第r輪ID號為i的節點的能距因子。

由于單鏈承擔了較多的數據收集與轉發的任務，在數據傳輸階段可能會能量耗盡，為了網絡鏈路的完整，需要對鏈進行維護。后文中提出替換方案對鏈進行維護。將鏈上低能量根節點的匯聚轉發工作轉交給附近探測范圍內能量最大的節點同時該根節點變成普通節點以節省能量。

文獻[13]提出簇首成鏈，本文優化為帶有距離和能量自適應性的能量樹根節點成鏈，使節點鏈路連接的方式多元化，并減少了完成一輪通信的最大傳輸距離。與文獻[16]的所有節點成單個最小生成樹和文獻[17]的距離門限相比，更具有能量適應性，而且探測范圍為到最近簇首，相當于對長鏈的一個距離門限，而偏遠節點的探測范圍相對更大，能獲得更大區域中更多節點鏈路轉發的支持，故是一個動態的距離門限，更具對節點地理位置的適應性。

2.6 數據傳輸階段

能量樹內普通成員根據TDMA時隙表并調節到父節點能接受到的最小發射功率發送信息，父節點收到數據后與自己采集的數據進行融合后再發往其自身父節點。同時過程受令牌控制，防止數據重復提交。單鏈再由鏈首節點產生Token，并將Token發往單鏈的任意一端，然后鏈首節點再將Token發往主鏈另外一端，最后鏈首節點將兩端傳來的數據經過融合后，傳輸到Sink節點。

所謂線上線下“雙師課堂”，即由一位名師通過視頻在線上直播自己的講課，而在線下的實體課堂里還有一位輔導老師負責在現場為學生答疑解惑。[2]這種課堂并不完全都是兩個教師的“1+1”模式，多數情況下是“1+N”模式的，即一個名師線上上課，同時有N個線下實體課堂在學習該課程，N個線下課堂里配備N個輔導老師進行現場輔助教學。

2.7 低能量的樹根節點替換方案

當簇首或大能量節點在轉發信息的過程中，能量低于閾值M時，先向全網廣播自己放棄擔任簇首和告知頂替自己任務的節點的消息，再將自己的一個標志位CantbeCH_flag設置為1，將信息轉發至其探測范圍內剩余能量最大的節點（非簇首節點優先），由其擔任自身的角色。

3 能耗分析

根據如前所述的無線傳感網絡特點，對ECRC算法能量模型作如下假設：網絡能量耗費主要在數據發送、數據接收和數據融合三個方面。成鏈階段的能量耗費相對整個數據傳送階段是很小的，忽略不計。而在實際中，因接收機不收數據時可關閉接收機，所以接收機接收不是發給自己的數據的能量耗費可不計。在本文中采用目前比較常用的傳感器節點工作能耗模型，將一個k-bit的信息傳送距離d，無線通信模塊的發送能耗和接收能耗分別為：

式中，Eelec表示傳感器無線發射電路(TE)或無接收電路(RE)發送或接收每bit數據的能耗，Efs表示發射放大器將每bit數據傳送單位平方米所耗的能量，ETx-elec(k)、ETx-amp(k，d)、ERx-elec(k)分別表示發射電路、發射電路放大器和接收電路的能耗，r為傳播衰減指數，其取值由周圍環境決定，在仿真中與實際距離閾值d0相比較，取2或4。并且比較結果也導致發射電路放大器能耗一項取不同的系數。

其中Efs為自由空間信號放大倍數。Emp為多徑衰減信道信號放大倍數。

n個能量樹根節點的無線傳感器網絡沿著單鏈傳輸k-bit的數據到鏈首節點所消耗的能量為：

式子中的d(i，j)表示鏈上兩個節點ni到nj的通信距離。

能量樹根節點所成的單鏈上從末梢節點到鏈首節點數據融合消耗的能量為：

不同節點承擔的角色分為：單簇首（也是能量樹根節點之一）；能量樹中非根節點的父節點；能量樹根節點；作為能量樹根的子節點的簇首；鏈首（也是能量樹根節點之一）節點；普通葉子節點。簇首和普通節點一樣，在選出后可以根據節點環境在這些角色中自適應地選擇，這是本文算法的核心之一。

4 仿真分析

使用MATLAB進行仿真，導入相同的隨機節點分布場景，并在相同參數設置下與PEGASIS協議、HCTRP協議和LEACH-P協議的仿真結果進行比較。

4.1 仿真參數設置

預先設定的MATLAB仿真環境主要參數如表1。

表1MATLAB仿真環境主要參數

并且為了實現對成簇間隔Q的控制，通過以下的公式完成對于其數值的漸變：

通過反復實驗，800輪左右網絡中出現死亡節點，為了均衡對節點能量的消耗，并將死亡節點出現的輪數延后和低能量狀態下的能耗均勻分布，設定800輪之后為每輪分簇。

開始時Q值為5，之后每隔200輪Q的值減去1，到800輪以后通過程序設定為1的固定值。

4.2 實驗結果和分析

如圖5所示，本文算法中的簇首選擇性地將數據轉發給到附近的最大能量節點（當附近沒有比其簇首自身能量大的節點時，選擇自身擔任能量樹的根節點，如圖中間的簇首）。簇首和能量樹根節點分布均勻，沒有長鏈，確保近簇區域內的節點的數據收集的同時，也保證節點不會跨越到簇頭距離的半徑去發送數據給大能量節點。

圖5 新算法的鏈路圖（簇首用長方形標示出）

如圖6所示，與PEGASIS、HCTRP和LEACH-P算法相比，ECRC算法在節點總能量消耗上更均衡。

圖6 網絡節點能量圖

如圖7所示，與PEGASIS、HCTRP算法相比，ECRC算法在存活節點個數上的開始死亡的時間延后了300輪左右，延長了37%。在節點全部死亡，網絡失效時間上比PEGASIS和HCTRP推遲了600輪的時間，提高了50%。比LEACH-P推遲了400輪的時間，提高了29%，對網絡所有節點的利用率更高。能量樹根節點相連成鏈，回避了長鏈傳輸，每跳傳輸能耗都趨于平均值。由于節點將信息向能量樹根節點匯聚，將融合和長距離發送數據的負擔轉移到了在多個探測距離的迭代范圍內具有大能量的節點上，起到了延長網絡生命周期的作用。

圖7 節點存活數目圖

5 結語

本文提出了一種簇首角色自適應能量樹成鏈算法。該算法將在不同的區域均勻分布的能量樹結構連接成單鏈。算法不是簇，樹，鏈三種結構的簡單疊加，而是通過簇首的多角色自適應選擇將每種結構的特色和優點發揮。簇更適用于簇間短距離通信，樹適用于對能耗的層次轉移，用多跳和子節點的方式協助低能量節點轉發信息而避免長距離發送而能量耗盡失效。鏈連接所有根節點能減少多簇首的消耗，但太多跳會有延遲，長鏈會有較大能耗。本文算法避免了多簇首與sink通信，而且單鏈路徑上沒有長鏈和交叉。實驗表明，新算法在生存時間、能耗均衡等方面較PEGASIS、HCTRP和LEACH-P算法有明顯改進。

[1]Estrin D.Wireless Sensor Networks tutorial part IV：sensor network protocols[R].Westin Peachtree Plaza，Atlanta，Georgia，USA，2002：23-28.

[2]Heinzelman，Rabiner W，Kulik J，et al.Adaptive protocols for information dissemination in wireless sensor networks[C]//The 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking，1999：174-185.

[3]Intanagonwiwat C，Govindan R，Estrin D.Directed diffusion：a scalable and robust communication paradigm for sensor networks[C]//Proc of Mobicom，Boston，2000.

[4]Braginsky，David，Estrin D.Rumor routing algorithm for sensor networks[C]//Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications，2002.

[5]Heinzelman W R，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless micro sensor networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[6]Lindsey S，Raghavendra C S.Power efficient gathering in sensor information systems[J].IEEE Aerospace Conference Proceedings，2002，3（3）：1125-1130.

[7]Manjeshwar，Arati，Agrawal D P.A routing protocol for enhanced efficiency in wireless sensor networks[C]//IEEE Parallel and Distributed Processing Symposium，2001：2009-2015.

[8]Baker D J，Ephremides A.The architectural organization of a mobile radio network via a distributed algorithm[J]. IEEE Transactions on Communications，1981，29（11）：1694-1701.

[9]Ding P，Holliday J，Celik A.Distributed energy efficient hierarchical clustering for wireless sensor networks[C]// Proceedings of the IEEE International Conference on Distributed Computing in Sensor Systems，Marina Del Rey，CA，2005.

[10]Chan H，Perring A.An emergent algorithm for highly uniform cluster formation[C]//Proceedings of the 1st European Workshop on Sensor Networks（EWSN），Berlin，Germany，2004.

[11]Demirbas M，Arora A，Mittal V.A fast local clustering service for wireless sensor networks[C]//Proceedings of Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks，Palazzo dei Congressi，Florence，Italy，2004.

[12]王波，蔣衛，孫燚.改進PEGASIS的分層鏈樹路由協議[J].計算機系統應用，2009（12）.

[13]張震，閆連山，潘煒.基于LEACH和PEGASIS的簇頭成鏈可靠路由協議研究[J].傳感器技術學報，2010，23（8）.

[14]霍建營.無線傳感器網絡分簇路由協議的研究[D].南京：南京郵電大學，2013.

[15]余勇昌，韋崗.無線傳感器網絡中基于PEGASIS協議的改進算法[J].電子學報，2008，36（7）.

[16]周潔，石志東，張震.WSN中一種基于LEACH協議的改進算法[J].上海大學學報，2013，19（2）.

[17]廖倩.基于能量均衡的無線傳感器網絡LEACH協議的研究[D].鄭州：鄭州大學，2013.

[18]古曉輝.無線傳感器網絡中基于梯度的有網關分簇拓撲控制研究[D].鄭州：鄭州大學，2013.

[19]寧林.無線傳感器網絡中基于TLEACH協議的研究[D].長沙：長沙理工大學，2013.

GUAN Xin1,WANG Jie2,TAO Zhiyong1

1.School of Electronics and Information Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China
2.Institute of Graduate,Liaoning Technical University,Huludao,Liaoning 125105,China

In previous routing protocol,the topologies of cluster,tree and chain are simple,and the distribution of cluster heads is irrational.The problem of long chain and crosses also troubles single-chain protocol.In response to this phenomenon, this paper proposes an Energy-tree Chain algorithm of Role-adaptive Cluster head（ECRC）.It liberates the cluster heads from fixed role and constructs secondary topology adaptively.Nodes form energy trees adaptively,the roots of which form into a single chain and combine the advantages of chain,tree and cluster.Simulation results show that this algorithm achieves better results in balancing energy consumption between nodes,and prolonging the network lifetime.

routing protocol;reference points;cluster head;energy tree;single chain;role-adaptive

以往的路由協議中，分簇，成樹，成鏈算法的拓撲結構單一，簇首分布不合理，單鏈存在長鏈和交叉的問題，且簇首無法自適應地轉換角色融入節點環境。由此，提出簇首角色自適應能量樹鏈算法（ECRC），將簇首從固定角色中解脫，能自適應地進行拓撲的二次構建。節點自適應形成能量樹結構，而能量樹根節點成單鏈將簇、樹、鏈優勢結合。仿真結果對比表明，該算法能有效地均衡節點間能耗、延長網絡生命周期。

路由協議；參考點；簇首；能量樹；單鏈；角色自適應

A

TP393

10.3778/j.issn.1002-8331.1404-0273

GUAN Xin,WANG Jie,TAO Zhiyong.Energy-tree chain algorithm of role-adaptive cluster head in WSN.Computer Engineering and Applications,2014,50（24）：70-75.

關昕（1967—），男，副教授，碩士生導師，主要研究方向：網絡安全；王杰（1990—），通訊作者，男，碩士研究生，主要研究方向：無線傳感器網絡；陶志勇（1978—），男，博士研究生，副教授，主要研究方向：多媒體通信。E-mail：705892335@qq.com

2014-04-17

2014-06-03

1002-8331（2014）24-0070-06

CNKI網絡優先出版：2014-07-16，http∶//www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1404-0273.html

book=75,ebook=80