關(guān) 昕，王 杰，陶志勇

1.遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105

2.遼寧工程技術(shù)大學(xué) 研究生學(xué)院，遼寧 葫蘆島 125105

WSN中簇首角色自適應(yīng)能量樹鏈算法

關(guān) 昕1，王 杰2，陶志勇1

1.遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105

2.遼寧工程技術(shù)大學(xué) 研究生學(xué)院，遼寧 葫蘆島 125105

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

1 相關(guān)路由協(xié)議

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

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

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

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

2.1 算法中的變量參數(shù)設(shè)定

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

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

（3）Q為成簇的間隔輪數(shù)。是輪數(shù)r的函數(shù)，在仿真環(huán)節(jié)具體設(shè)置。

（4）T為對簇首的位置和個數(shù)的輪數(shù)限制。開始時簇首個數(shù)為5且受到參考節(jié)點的限制。T輪后簇首的個數(shù)可以小于5，并且由選簇首的閾值T2(n)判斷隨機選出的節(jié)點是否擔(dān)任簇首?；趯嶒炗^測首個死亡節(jié)點出現(xiàn)的輪數(shù)的期望來進行設(shè)置。

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

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

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

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

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

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

2.2 參考點設(shè)置

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

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

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

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

圖1 L1～L4

圖2 L5

圖3 100×100

增設(shè)參考點可以將多個（100×100）區(qū)域拼接在一起（如200×100）。根據(jù)實際監(jiān)測區(qū)域面積對參考點個數(shù)進行設(shè)置。

2.3 簇頭選舉階段

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

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

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

算法流程圖如圖4所示。

圖4 算法流程圖

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

2.4 能量樹建立階段

本文首次提出使節(jié)點探測和發(fā)送的距離為每個節(jié)點到最近簇首的距離以適應(yīng)最近的轉(zhuǎn)發(fā)點形成合理的多跳路由樹。該階段的目標是在全網(wǎng)中建立各自獨立且均勻分布的能量樹結(jié)構(gòu)。

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

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

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

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

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

（6）能量樹根節(jié)點（可以是大能量的普通節(jié)點或大能量的簇首節(jié)點）將收到的信息數(shù)據(jù)融合后準備進行轉(zhuǎn)發(fā)。

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

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

2.5 能量樹根節(jié)點成鏈階段

本文首次將簇，樹，鏈三種結(jié)構(gòu)有效地結(jié)合在一起，提出能量樹成鏈的方法，與簇首或簇內(nèi)最小生成樹成鏈有很大不同，主要體現(xiàn)在能量和距離的適應(yīng)性上。該階段的目標是把全網(wǎng)中已經(jīng)建立好的各自獨立能量樹結(jié)構(gòu)的根節(jié)點用單鏈串聯(lián)起來。

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

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

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

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

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

2.6 數(shù)據(jù)傳輸階段

能量樹內(nèi)普通成員根據(jù)TDMA時隙表并調(diào)節(jié)到父節(jié)點能接受到的最小發(fā)射功率發(fā)送信息，父節(jié)點收到數(shù)據(jù)后與自己采集的數(shù)據(jù)進行融合后再發(fā)往其自身父節(jié)點。同時過程受令牌控制，防止數(shù)據(jù)重復(fù)提交。單鏈再由鏈首節(jié)點產(chǎn)生Token，并將Token發(fā)往單鏈的任意一端，然后鏈首節(jié)點再將Token發(fā)往主鏈另外一端，最后鏈首節(jié)點將兩端傳來的數(shù)據(jù)經(jīng)過融合后，傳輸?shù)絊ink節(jié)點。

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

2.7 低能量的樹根節(jié)點替換方案

當簇首或大能量節(jié)點在轉(zhuǎn)發(fā)信息的過程中，能量低于閾值M時，先向全網(wǎng)廣播自己放棄擔(dān)任簇首和告知頂替自己任務(wù)的節(jié)點的消息，再將自己的一個標志位CantbeCH_flag設(shè)置為1，將信息轉(zhuǎn)發(fā)至其探測范圍內(nèi)剩余能量最大的節(jié)點（非簇首節(jié)點優(yōu)先），由其擔(dān)任自身的角色。

3 能耗分析

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

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

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

n個能量樹根節(jié)點的無線傳感器網(wǎng)絡(luò)沿著單鏈傳輸k-bit的數(shù)據(jù)到鏈首節(jié)點所消耗的能量為：

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

能量樹根節(jié)點所成的單鏈上從末梢節(jié)點到鏈首節(jié)點數(shù)據(jù)融合消耗的能量為：

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

4 仿真分析

使用MATLAB進行仿真，導(dǎo)入相同的隨機節(jié)點分布場景，并在相同參數(shù)設(shè)置下與PEGASIS協(xié)議、HCTRP協(xié)議和LEACH-P協(xié)議的仿真結(jié)果進行比較。

4.1 仿真參數(shù)設(shè)置

預(yù)先設(shè)定的MATLAB仿真環(huán)境主要參數(shù)如表1。

表1MATLAB仿真環(huán)境主要參數(shù)

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

通過反復(fù)實驗，800輪左右網(wǎng)絡(luò)中出現(xiàn)死亡節(jié)點，為了均衡對節(jié)點能量的消耗，并將死亡節(jié)點出現(xiàn)的輪數(shù)延后和低能量狀態(tài)下的能耗均勻分布，設(shè)定800輪之后為每輪分簇。

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

4.2 實驗結(jié)果和分析

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

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

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

圖6 網(wǎng)絡(luò)節(jié)點能量圖

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

圖7 節(jié)點存活數(shù)目圖

5 結(jié)語

本文提出了一種簇首角色自適應(yīng)能量樹成鏈算法。該算法將在不同的區(qū)域均勻分布的能量樹結(jié)構(gòu)連接成單鏈。算法不是簇，樹，鏈三種結(jié)構(gòu)的簡單疊加，而是通過簇首的多角色自適應(yīng)選擇將每種結(jié)構(gòu)的特色和優(yōu)點發(fā)揮。簇更適用于簇間短距離通信，樹適用于對能耗的層次轉(zhuǎn)移，用多跳和子節(jié)點的方式協(xié)助低能量節(jié)點轉(zhuǎn)發(fā)信息而避免長距離發(fā)送而能量耗盡失效。鏈連接所有根節(jié)點能減少多簇首的消耗，但太多跳會有延遲，長鏈會有較大能耗。本文算法避免了多簇首與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，F(xiàn)lorence，Italy，2004.

[12]王波，蔣衛(wèi)，孫燚.改進PEGASIS的分層鏈樹路由協(xié)議[J].計算機系統(tǒng)應(yīng)用，2009（12）.

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

[14]霍建營.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議的研究[D].南京：南京郵電大學(xué)，2013.

[15]余勇昌，韋崗.無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的改進算法[J].電子學(xué)報，2008，36（7）.

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

[17]廖倩.基于能量均衡的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的研究[D].鄭州：鄭州大學(xué)，2013.

[18]古曉輝.無線傳感器網(wǎng)絡(luò)中基于梯度的有網(wǎng)關(guān)分簇拓撲控制研究[D].鄭州：鄭州大學(xué)，2013.

[19]寧林.無線傳感器網(wǎng)絡(luò)中基于TLEACH協(xié)議的研究[D].長沙：長沙理工大學(xué)，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

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

路由協(xié)議；參考點；簇首；能量樹；單鏈；角色自適應(yīng)

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.

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

2014-04-17

2014-06-03

1002-8331（2014）24-0070-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-07-16，http∶//www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1404-0273.html

book=75,ebook=80