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

關(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ú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）中無(wú)線通信單元是消耗能量主要單元[1]。傳感器節(jié)點(diǎn)能量有限且無(wú)法補(bǔ)充。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的合理性影響高層通信協(xié)議的執(zhí)行和網(wǎng)絡(luò)運(yùn)行能耗，且傳輸比運(yùn)算處理一個(gè)比特的能耗大很多倍[1]。從節(jié)點(diǎn)參與通信的拓?fù)浜头绞?，可以將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é)議

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（8）Ci為前T輪共用的簇首標(biāo)記位。

2.2 參考點(diǎn)設(shè)置

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

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

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

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

圖1 L1～L4

圖2 L5

圖3 100×100

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

2.3 簇頭選舉階段

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

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

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

算法流程圖如圖4所示。

圖4 算法流程圖

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

2.4 能量樹建立階段

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

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

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

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

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

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

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

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

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

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

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

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

（3）由離sink最遠(yuǎn)到最后一個(gè)節(jié)點(diǎn)，用貪婪算法一跳跳地連接起來(lái)。

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

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

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

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

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

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

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

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

3 能耗分析

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

式中，Eelec表示傳感器無(wú)線發(fā)射電路(TE)或無(wú)接收電路(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)境決定，在仿真中與實(shí)際距離閾值d0相比較，取2或4。并且比較結(jié)果也導(dǎo)致發(fā)射電路放大器能耗一項(xiàng)取不同的系數(shù)。

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

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

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

能量樹根節(jié)點(diǎn)所成的單鏈上從末梢節(jié)點(diǎn)到鏈?zhǔn)坠?jié)點(diǎn)數(shù)據(jù)融合消耗的能量為：

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

4 仿真分析

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

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

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

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

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

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

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

4.2 實(shí)驗(yàn)結(jié)果和分析

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

圖5 新算法的鏈路圖（簇首用長(zhǎng)方形標(biāo)示出）

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

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

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

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

5 結(jié)語(yǔ)

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

[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)，孫燚.改進(jìn)PEGASIS的分層鏈樹路由協(xié)議[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2009（12）.

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

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

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

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

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

[18]古曉輝.無(wú)線傳感器網(wǎng)絡(luò)中基于梯度的有網(wǎng)關(guān)分簇拓?fù)淇刂蒲芯縖D].鄭州：鄭州大學(xué)，2013.

[19]寧林.無(wú)線傳感器網(wǎng)絡(luò)中基于TLEACH協(xié)議的研究[D].長(zhǎng)沙：長(zhǎng)沙理工大學(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é)議中，分簇，成樹，成鏈算法的拓?fù)浣Y(jié)構(gòu)單一，簇首分布不合理，單鏈存在長(zhǎng)鏈和交叉的問(wèn)題，且簇首無(wú)法自適應(yīng)地轉(zhuǎn)換角色融入節(jié)點(diǎn)環(huán)境。由此，提出簇首角色自適應(yīng)能量樹鏈算法（ECRC），將簇首從固定角色中解脫，能自適應(yīng)地進(jìn)行拓?fù)涞亩螛?gòu)建。節(jié)點(diǎn)自適應(yīng)形成能量樹結(jié)構(gòu)，而能量樹根節(jié)點(diǎn)成單鏈將簇、樹、鏈優(yōu)勢(shì)結(jié)合。仿真結(jié)果對(duì)比表明，該算法能有效地均衡節(jié)點(diǎn)間能耗、延長(zhǎng)網(wǎng)絡(luò)生命周期。

路由協(xié)議；參考點(diǎn)；簇首；能量樹；單鏈；角色自適應(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ú)線傳感器網(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