SAHRC: 一種基于分簇的無線傳感器網絡路由控制算法

張小波 程良倫 Zhu Quan-min

①(廣東工業(yè)大學自動化學院 廣州 510006)

②(英國西英格蘭大學計算機工程與數(shù)學學院 布里斯托爾 BS161QY)

1 引言

無線傳感器網絡建設最主要考慮的問題之一就是降低全網能耗。路由控制算法是達到這一目標的重要手段之一。路由控制算法從研究方向進行分類可以分為：節(jié)點功率控制算法、層次型控制算法、網內節(jié)點協(xié)同啟發(fā)機制[1]。節(jié)點功率控制機制調節(jié)網絡中每個節(jié)點的發(fā)射功率，目的是在保證全網連通性的情況下，均衡節(jié)點一跳距離的鄰居數(shù)量。經典算法有：LMA[2]、DRNG[3]等；層次型控制算法是選擇網絡中的一些節(jié)點做為骨干節(jié)點，構架起包轉發(fā)的骨干網絡，其他非骨干網節(jié)點接受骨干節(jié)點管轄；網內節(jié)點協(xié)同啟發(fā)機制是節(jié)點按照周邊通信環(huán)境的變化，進行自主控制以及和鄰居節(jié)點進行交互的機制，經典算法有：STEM算法[4,5]，ASCENT算法[6,7]等。無線傳感器網絡實際中面對的是隨機部署的大規(guī)模密集型網絡，經典的路由控制機制無法適應無線傳感器網絡應用場合的特殊要求，特別是針對大規(guī)模事件驅動型網絡的應用場合。功率控制由于缺乏休眠機制而無法適應大規(guī)模密集型網絡。層次型控制可以近似地用于大規(guī)模網絡但是缺乏本地功率優(yōu)化和自適應性。而協(xié)同啟發(fā)機制的缺點在于局部的自適應性不能很好地擴展到大規(guī)模網絡。除此之外，大多數(shù)算法都沒有考慮節(jié)點剩余能量和負載均衡問題。

針對這一問題，通過結合各種路由控制機制的優(yōu)勢來構建一種適應于大規(guī)模事件驅動型網絡場景的無線傳感器網絡路由控制算法。在這種場合下，興趣事件的低概率發(fā)生使得網絡中傳遞的數(shù)據量較小，因此大部分能耗會流失在節(jié)點偵聽環(huán)節(jié)，所以降低網絡的偵聽能耗成為延長無線傳感器網絡生命期的特性因素和主要手段，同時該場景下路由控制算法的設計還必須符合傳統(tǒng)算法設計的共性原則[8]。回顧以往面向事件驅動型網絡經典算法有GAF[9],LEACH[10]等；本文在研究LEACH算法分簇機制思想[11]的基礎上結合網內節(jié)點啟發(fā)機制改善設計一種自適應的混合型路由控制(Self-Adaptive Hybrid Routing Control, SAHRC)算法。仿真結果表明，改進后的算法較原有算法有更好的穩(wěn)定性和可靠性。

2 LEACH算法的局限及SAHRC算法的提出

LEACH算法具有以下不足：

(1)由于LEACH 算法中簇頭產生的隨機性，會導致部分簇頭相距過近或簇頭處于網絡邊緣，簇內成員離簇頭太遠的情況，從而大大增加了節(jié)點的傳輸能耗。

(2)由于LEACH 簇頭選擇的隨機性，使得網絡中簇頭節(jié)點所負擔的簇內成員數(shù)不同(即每個簇頭節(jié)點的節(jié)點度不同)，加重了個別簇頭節(jié)點的負擔，使得網絡的負載平衡度下降。

(3)LEACH算法在簇頭選舉過程中，沒有考慮節(jié)點的剩余能量狀態(tài)，會出現(xiàn)某一節(jié)點的剩余能量很小，但仍被當選為簇頭的情況。

(4)LEACH算法并沒有考慮到網絡熱區(qū)問題。網絡熱區(qū)問題指的是網絡中距離匯聚節(jié)點越近的節(jié)點傳輸信息的頻率就會越大，而越是離匯聚節(jié)點遠的簇頭節(jié)點負責轉發(fā)信息的負擔就會越小。

本文針對以上不足提出一種自適應混合型路由控制算法——SAHRC算法，該算法是在LEACH分簇思想的基礎上，結合了網內節(jié)點啟發(fā)機制，使原有算法更適應于大規(guī)模事件驅動型網絡。

3 SAHRC算法設計

3.1 SAHRC算法描述

SAHRC算法在沿用LEACH算法的原有分簇機制的基礎上引入網內節(jié)點啟發(fā)機制思想，使得算法更適應于大規(guī)模網絡。在分簇之后的網內通信和簇間通信都利用了啟發(fā)機制的思想。

(1)相關定義

CM(Cluster Member)：簇內節(jié)點，非簇頭節(jié)點。

CH(Cluster Head)：簇頭節(jié)點。

Ei：節(jié)點i當前剩余能量。

TEST消息：TEST消息發(fā)送成功則節(jié)點發(fā)送包含自身ID號的HELLO消息，表示自身成為簇頭。節(jié)點若已經是簇頭，或者已經屬于某一個簇，則不發(fā)送TEST消息。

節(jié)點信息：一個節(jié)點的節(jié)點信息包括自身ID及剩余能量值Ei。

CLUSTER消息：由簇頭節(jié)點發(fā)送，告知簇內節(jié)點簇頭節(jié)點的ID與En，及該簇內部所有節(jié)點之間的鄰居節(jié)點關系和Ei。收到該消息的簇內節(jié)點記錄自身處于哪一個簇，并確定鄰居節(jié)點，調整發(fā)送功率。

HELP消息：用來把節(jié)點由偵聽狀態(tài)轉入測試狀態(tài)或由測試狀態(tài)轉入活動狀態(tài)的直接依據。

時間域值Ta：在時間Ta內如果沒有消息轉發(fā)，則認為該節(jié)點可以由活動狀態(tài)轉入休眠狀態(tài)。

(2)SAHRC算法步驟

步驟1 分簇

(a)簇首選擇機制 LEACH算法中，隨機簇首選擇機制保證了網絡的自組織特性，但并沒有將剩余能量作為簇首選擇的條件，本文在簇首選擇中加入了剩余能量和平均能量的考慮，從而優(yōu)化了LEACH的簇首選擇機制。在每一輪的簇重構之前，節(jié)點都查看其當前剩余能量Erest和上一輪末節(jié)點所屬簇的平均剩余能量Eaverage。當Erest≥Eaverage時，此節(jié)點產生隨機數(shù)，參與候選簇首競爭；反之，當Erest＜Eaverage時，節(jié)點能量有限，則節(jié)點就處于休眠狀態(tài)，不參與候選簇首競爭，直至候選簇首競爭結束。在LEACH中，采用隨機數(shù)小于閾值的方式選為簇首，簇首的產生具有極大的隨機性，容易出現(xiàn)部分簇首剩余能量相對較小但仍被選為簇首的情況，此時節(jié)點的能量就會很快耗盡，不利于延長整個網絡的使用壽命。基于以上考慮，各節(jié)點采取隨機數(shù)生成策略：若節(jié)點參與候選簇首競爭，則隨機地產生一個初始隨機數(shù)，將節(jié)點剩余能量與初始能量的比值的負指數(shù)函數(shù)作為臨時隨機數(shù)的大小調節(jié)因子來產生最終隨機數(shù)，利用單調遞減的負指數(shù)函數(shù)對產生的隨機數(shù)作進一步的調整。剩余能量越大的節(jié)點產生的最終隨機數(shù)越小，越容易小于當前閾值，也就越容易成為本輪的候選簇首；而剩余能量越小的節(jié)點調節(jié)因子越大，產生的最終隨機數(shù)也越大，越不容易成為本輪候選簇首。這樣使得能量大節(jié)點盡可能容易地成為候選簇首，平衡了網絡能量負載，可以延長網絡壽命。

式中rand(i)是節(jié)點i與閾值比較的最終隨機數(shù)，temp(i)是節(jié)點i生成的0～1間的初始隨機數(shù)，E(i)是節(jié)點i此時的剩余能量，E0是節(jié)點i的初始能量。若rand(i)小于閾值T(n)，這個節(jié)點i就成為候選簇首。T(n)的計算公式與LEACH算法中類似。

(b)簇的生成算法 通過簇首選擇機制產生了一定比例的候選簇首，這些候選簇首通過競爭產生本輪正式簇首，而其他節(jié)點處于休眠狀態(tài)直至簇首競爭結束。

在競爭初始階段，基站在整個區(qū)域內以一定的發(fā)射功率廣播TEST消息，每個候選簇首根據收到的消息的強弱程度計算自身到基站的距離?？紤]到非均勻分簇能夠很好地解決多跳路由的傳感器網絡中常見的熱區(qū)問題，這里提出的計算競爭半徑的公式如下：

其中R是簇首si的競爭半徑，c是用來控制取值范圍的參數(shù)，在0～1之間取隨機值。當c值取0時，算法分成大小均勻的簇；當c大于0.5后，網絡的存活時間逐漸下降，這是由于算法產生的簇首的數(shù)量逐漸增加，增大了網絡的能量消耗。Dmax和Dmin分別表示網絡中節(jié)點到基站BS的距離的最大值和最小值，D(si,BS)表示簇首si到基站的距離，Rmax是預先定義好的最大的競爭半徑。每個候選簇首得到自身的競爭半徑后，在自己的競爭區(qū)域內廣播競爭簇首的消息。若在它的競爭區(qū)域內沒有其他候選節(jié)點，則此候選簇首競爭成功，并在整個網絡中廣播競爭成功的消息；若在自己的競爭區(qū)域內存在其他候選簇首，則比較各個候選簇首的剩余節(jié)點能量，剩余節(jié)點能量較大的競爭成功，并廣播此消息，其他候選簇首退出競爭；網絡中的其他節(jié)點根據接收到的信息的強度加入各個簇中，若有節(jié)點未收到任何一個簇首發(fā)來的消息，則此節(jié)點成為候選簇首參與競爭。最后，網絡中的所有節(jié)點都成為簇首或簇內成員。由此保證了監(jiān)測區(qū)域中所有節(jié)點形成的監(jiān)測范圍可以滿足應用需求，任何一個節(jié)點都能將感知到的數(shù)據發(fā)送到簇首，再由簇首轉發(fā)給基站，而不會產生網絡分隔，從而可以保證簇節(jié)點的連通與覆蓋。簇內成員向簇首發(fā)送加入消息并將自身的剩余能量告訴簇首，簇首就知道了簇內成員的總數(shù)并在得到各個節(jié)點的能量信息后計算簇內平均能量并將此消息在簇內廣播，此時整個網絡的簇結構基本確定。

規(guī)則1 在網絡成簇過程中如果預備簇首發(fā)現(xiàn)自己的簇內還有另外一個或一個以上的預備簇首，則通過距離匯聚節(jié)點的遠近將優(yōu)先選擇離匯聚節(jié)點較近的節(jié)點作為這個簇的簇頭。

規(guī)則2 在網絡成簇過程中，如果簇首發(fā)現(xiàn)自己的節(jié)點度已經超過了6或者以上時則自動分為兩個簇，并選擇簇內成員節(jié)點密集處優(yōu)先成簇。如果簇首發(fā)現(xiàn)自己的節(jié)點度小于4或者更少時，則主動與鄰居簇結合成一個簇。

規(guī)則3 如果在全網簇首選擇過程中發(fā)現(xiàn)某些靠近匯聚節(jié)點的節(jié)點或熱區(qū)節(jié)點能量消耗過多時要優(yōu)先考慮離匯聚節(jié)點較遠的節(jié)點作為候選簇首。

步驟2 簇內通信

簇內通信采用局部的ASCENT算法，不同的是從數(shù)據源發(fā)起求助信息，并考慮節(jié)點剩余能量問題。

(a)在初始化階段，所有節(jié)點進入測試階段。開始由任一數(shù)據源發(fā)起HELP消息，發(fā)給節(jié)點剩余能量較為高的鄰居節(jié)點。

(b)鄰居節(jié)點加入活動節(jié)點一起轉發(fā)數(shù)據，如此反復直到本簇的簇頭節(jié)點加入活動節(jié)點。

規(guī)則4 如果節(jié)點發(fā)現(xiàn)自己的鄰居中有簇頭節(jié)點，則直接選擇該節(jié)點充當活動節(jié)點并轉到步驟3的(a)步，如果節(jié)點發(fā)現(xiàn)自己的鄰居中沒有簇頭節(jié)點，但是有關聯(lián)節(jié)點，則選擇關聯(lián)節(jié)點充當活動節(jié)點并轉到步驟3的(b)步。

規(guī)則5 在規(guī)則4的基礎上， 如果節(jié)點發(fā)出HELP消息之后，發(fā)現(xiàn)丟包率仍然高于丟包臨界(DL)，則選擇剩余能量次高的鄰居，要求其加入活動節(jié)點。依此類推，直到發(fā)現(xiàn)鄰居數(shù)量高于鄰居臨界(NL)為止。

步驟3 簇間通信

在簇間仍然使用ASCENT規(guī)則來完成數(shù)據的轉發(fā)。

(a)當某一簇頭節(jié)點CH加入活動節(jié)點之后，向匯聚節(jié)點方向的關聯(lián)節(jié)點發(fā)布HELP消息。選擇剩余能量大的關聯(lián)節(jié)點加入到網絡中。

(b)該關聯(lián)節(jié)點再向匯聚節(jié)點方向的簇頭發(fā)送HELP消息。如此反復直到把消息傳送給匯聚節(jié)點。

規(guī)則6 對于孤立簇，如果簇頭沒有收到簇內節(jié)點的CONECTNODE消息時，則要求所有的簇內節(jié)點探測自身的鄰居節(jié)點，加入關聯(lián)節(jié)點。

步驟4 網絡維護

當簇內節(jié)點失效數(shù)量達到一定的閾值或者網絡中有簇頭節(jié)點失效則重新進入簇頭選擇和全網待定狀態(tài)，也即等待網絡中隨機事件的發(fā)生。

經過SAHRC算法之后，理論上得到如圖1所示的SAHRC算法網絡拓撲結構分析圖。

3.2 SAHRC算法的狀態(tài)轉換機制

在SAHRC算法中，每一節(jié)點始終處于4種狀態(tài)中的任意一種：休眠(SLEEP)、偵聽(PASSIVE)、測試(TEST)、活動(ACTIVE)。

圖1 SAHRC算法網絡拓撲結構分析圖

初始狀態(tài)時一個隨機的定時器打開，任意節(jié)點在測試階段初始化。當一個節(jié)點進入測試階段時候，它就設定一個時間器Tt，當Tt期滿的時候，發(fā)送“鄰居聲明”消息，節(jié)點進入活動狀態(tài)。如果在Tt到來之前活動節(jié)點的數(shù)量超過了鄰居上限(NT)或者如果平均數(shù)據丟失率(DL)高于在自己處于測試階段時的平均數(shù)據丟失率時節(jié)點轉入偵聽狀態(tài)。如果多個節(jié)點同時轉入了測試狀態(tài)，就選擇在“鄰居聲明”消息里節(jié)點ID高的節(jié)點成為活動節(jié)點?；顒庸?jié)點的數(shù)量不能超過NT值。當一個節(jié)點進入偵聽態(tài)的時候，它設置了一個定時器Tp。當Tp時間到的時候，節(jié)點進入休眠狀態(tài)。如果在Tp到來之前鄰居數(shù)量低于NT，或者DL高于丟包臨界值(LT)，或者DL低于丟包臨界值但是節(jié)點收到了一個來自于活動鄰居的求助消息，節(jié)點就轉入到測試狀態(tài)。當在偵聽狀態(tài)時節(jié)點打開它們的射頻模塊，能夠監(jiān)聽到所有的活動鄰居傳送的包，但不傳送任何數(shù)據包。處于偵聽和測試狀態(tài)的節(jié)點，持續(xù)刷新活動鄰居的數(shù)量和數(shù)據丟失率的值。一個進入休眠態(tài)的節(jié)點關閉射頻模塊，設置一個時間Ts用來度量休眠長度，當Ts到了的時候，節(jié)點轉入偵聽模式。一個節(jié)點一旦進入活動狀態(tài)，就在活動狀態(tài)繼續(xù)傳遞數(shù)據和路由包直到它消耗完能量為止。如果數(shù)據丟失率高于LT時，活動的節(jié)點又開始發(fā)送求助消息。

所有網絡節(jié)點都按照4種狀態(tài)不停循環(huán)，并加入一個時間域Ta值，即如果在這個時間內活動節(jié)點不再轉發(fā)數(shù)據則主動轉入休眠狀態(tài)。這樣就大大節(jié)省了網絡資源的消耗，使得算法更加適用于事件驅動型網絡。這里Ta的值要通過實際事件發(fā)生概率的大小等因素而定。

4 模擬實驗與結果分析

這里通過OMNET++仿真工具進行模擬并分析SAHRC算法的性能。利用NED和INI配置文件描述下面實驗環(huán)境：N個節(jié)點隨機部署在100 m×100 m的正方形事件區(qū)域內。隨機選擇1個節(jié)點作為匯聚節(jié)點，p個節(jié)點作為源節(jié)點，源節(jié)點以速率v=5 kbps勻速獲知數(shù)據并發(fā)往匯聚節(jié)點。每個節(jié)點通信半徑50 m，節(jié)點初始能量10 J，節(jié)點偵聽能耗0.1 J。實驗中不考慮節(jié)點移動性和報文傳輸延時，并且忽略節(jié)點接收報文及處理器的能耗。模擬實驗的基本參數(shù)設定如表1所示。

表1 模擬實驗主要參數(shù)

為了盡量忽略由于Ta值導致的網絡性能不同，設Ta=20Tp。節(jié)點信號強度之比用距離平方的反比來表示。

4.1 網絡節(jié)能性實驗分析

實驗中采用一半節(jié)點死亡的時間作為網絡生存時間的評價標準。因為若網絡中一半節(jié)點死亡，剩余節(jié)點的能量已經很低，網絡的連通度也無法有效保證。網絡生存時間的對比如圖2所示，SAHRC的網絡生存期明顯高于LEACH，特別是隨著節(jié)點數(shù)量的增多，LEACH算法下網絡生存期增幅越來越小。這是因為一方面隨著網絡節(jié)點數(shù)量的增多，處于偵聽與活動狀態(tài)節(jié)點過多，造成了網絡不必要的消耗；另一方面由于活動節(jié)點無法進入休眠狀態(tài)而導致大部分節(jié)點過早死亡，出現(xiàn)網絡割裂現(xiàn)象。SAHRC算法在考慮剩余能量的基礎上加入網內節(jié)點啟發(fā)機制使得節(jié)點有效選擇鏈路而避免了過多節(jié)點加入到信息轉發(fā)中來，同時也達到了負載均衡的目的。而Ta和Tj參數(shù)的加入，很好地避免了節(jié)點早死現(xiàn)象。實驗表明SAHRC算法更適應于大規(guī)模事件驅動型網絡。

圖2 SAHRC與LEACH網絡生命期對比

4.2 網絡穩(wěn)定性實驗分析

實驗不斷增加模型節(jié)點數(shù)量參數(shù)，在與其相應的網絡生命期內統(tǒng)計兩種算法導致的匯聚節(jié)點收到數(shù)據包數(shù)量總和。由圖3可見，隨著節(jié)點的增加，SAHRC算法匯聚節(jié)點收到的數(shù)據包數(shù)在相應地增多，而且增幅較高。而LEACH算法匯聚節(jié)點收到的數(shù)據包數(shù)量在節(jié)點數(shù)少于200的時候還有一些增幅，但是當節(jié)點數(shù)接近200時匯聚節(jié)點收到的數(shù)據包數(shù)已經基本上不變，即增幅趨向于零。

圖3 SAHRC與LEACH數(shù)據包數(shù)量對比

仿真實驗表明，SAHRC算法延長了網絡生命周期，提高了網絡通信效率。改進了LEACH算法的節(jié)能性和穩(wěn)定性。

5 結束語

本文在LEACH算法的基礎上，設計了一種適用于大規(guī)模事件驅動型網絡的自適應混合型路由控制算法。該算法結合層次型路由算法的分簇思想以及節(jié)點網內啟發(fā)機制，擴大了原算法的應用場合，使網絡中剩余能量高的節(jié)點充當活動節(jié)點，延長了網絡生命周期，提高了網絡的通信效率。同時設定了活動節(jié)點狀態(tài)轉換域值，進一步降低了全網能耗。

[1] 楊賀, 張樹東, 孫利民. 無線傳感器網絡的拓撲控制機制[J].計算機科學, 2007, 34(1): 36-38.Yang He, Zhang Shu-dong, and Sun Li-min. Topology control mechanism in wireless sensor networks[J].Computer Science,2007, 34(1): 36-38.

[2] 鄧克波, 劉中. 基于感知距離調節(jié)的無線傳感器網絡節(jié)能區(qū)域覆蓋[J]. 電子與信息學報, 2009, 31(10): 2305-2309.Deng Ke-bo and Liu Zhong. Energy-efficient area coverage in wireless sensor networks with adjustable sensing ranges[J].Journal of Electronics&Information Technology, 2009,31(10): 2305-2309.

[3] Park Kyung-joon, Kim Laeyoung, and Hou J C. Adaptive physical carrier sense in topology-controlled wireless networks[J].IEEE Transactions on Mobile Computing,2010, 9(1): 87-97.

[4] Liu Yun-huai, Zhang Qian, and Ni L M. Opportunity-based topology control in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems, 2010,21(3): 405-416.

[5] Huang C M, Ku H H, and Kung H Y. Efficient powerconsumption-based load-sharing topology control protocol for harsh environments in wireless sensor networks[J].Communications,IET, 2009, 3(5): 859-870.

[6] Cerpa A and Estrin D. ASCENT: adaptive self-configuring sensor networks topologies[J].IEEE Transactions on Mobile Computing, 2004, 3(3): 272-285.

[7] White J, Doughtery B, and Schmidt D. ASCENT: an algorithmic technique for designing hardware and software in tandem[J].IEEE Transactions on Software Engineering,2010, 36(6): 838-851.

[8] 劉林峰, 金杉. 面向低概率事件場景的傳感器網絡分簇控制算法[J]. 計算機研究與發(fā)展, 2008, 45(10): 1662-1668.Liu Lin-feng and Jin Shan. A clustering control algorithm of wireless sensor networks in low probability event scenario[J].Journal of Computer Research and Development, 2008,45(10): 1662-1668.

[9] 沙超, 王汝傳, 黃海平, 等. 基于生命期劃分的無線傳感器網絡節(jié)能策略[J]. 通信學報, 2010, 31(4): 1-7.Sha Chao, Wang Ru-chuan, Huang Hai-ping,et al.. Energy saving scheme based on life period division for wireless sensor networks[J].Journal on Communications, 2010, 31(4): 1-7.

[10] Heinzelman W R, Chandrakasan A, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[11] 徐勁松, 楊庚, 陳生壽, 等. 基于全局信息的 LEACH 協(xié)議改進算法[J]. 南京郵電大學學報(自然科學版), 2009, 29(4):55-63.Xu Jing-song, Yang Geng, Chen Sheng-shou,et al.. A global information based protocol for LEACH improvement[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science), 2009, 29(4): 55-63.