一種基于交錯分鏈結(jié)構(gòu)的路由協(xié)議

蘇鵬舉，徐玉斌

(太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，太原 030024)

無線傳感器網(wǎng)絡(luò)綜合了微電子技術(shù)、網(wǎng)絡(luò)通信技術(shù)和傳感器技術(shù)等技術(shù)，應(yīng)用于軍事、醫(yī)療、交通、工業(yè)和民用等領(lǐng)域，具有巨大的應(yīng)用價值，引起了世界各國的高度重視[1-2]。它是由具有感知數(shù)據(jù)、無線通信能力和信息處理能力的傳感器節(jié)點組成。網(wǎng)絡(luò)中的節(jié)點之間以無中心的無線多跳方式連接，能夠協(xié)同工作，可以實時監(jiān)測和采集各種環(huán)境和監(jiān)測對象的相關(guān)信息。

無線傳感器網(wǎng)絡(luò)中的節(jié)點通常工作在野外較為惡劣的環(huán)境之中，能量是一般由電池來供應(yīng)。而電池的能量有限，并且難以在工作的時候更換，所以有限的節(jié)點能量決定了網(wǎng)絡(luò)的生存時間[3]。無線傳感器網(wǎng)絡(luò)的這個特點決定了傳統(tǒng)的路由協(xié)議在網(wǎng)絡(luò)中無法直接應(yīng)用，需要設(shè)計新的適用于無線傳感器網(wǎng)絡(luò)的節(jié)能路由協(xié)議。

LEACH[4]協(xié)議和 PEGASIS[5]協(xié)議是典型的無線傳感器網(wǎng)絡(luò)路由協(xié)議，本文在此基礎(chǔ)上，以均衡節(jié)點能耗和延長網(wǎng)絡(luò)生存周期為目標(biāo)，針對其不足進(jìn)行的改進(jìn)，提出了基于交錯分鏈結(jié)構(gòu)的路由協(xié)議，改進(jìn)后的協(xié)議在節(jié)能方面具有了更好的性能。

1 LEACH協(xié)議和PEGASIS協(xié)議

LEACH協(xié)議和PEGASIS協(xié)議是無線傳感器網(wǎng)絡(luò)路由協(xié)議中典型的分層路由協(xié)議。其中，LEACH協(xié)議是最早的分層路由協(xié)議。LEACH協(xié)議隨機的簇頭選舉機制，使得整個傳感器網(wǎng)絡(luò)的能量負(fù)載平均分配到每個節(jié)點上，延長了網(wǎng)絡(luò)生存周期。LEACH協(xié)議與一般的平面多跳路由協(xié)議以及靜態(tài)分層算法相比，生命周期延長了15%.其選擇簇頭的公式如下:

其中，p是網(wǎng)絡(luò)中簇頭數(shù)占所有節(jié)點數(shù)的百分比，也是節(jié)點可能擔(dān)當(dāng)簇頭的概率值;r是當(dāng)前運行的輪數(shù);G是在最近的1/p輪中還未曾擔(dān)任過簇頭的節(jié)點集合。在簇建立的時候，每個節(jié)點會產(chǎn)生一個界于0和1之間的隨機數(shù)字，與閾值T(n)進(jìn)行對比，如果小于該閾值，此節(jié)點就被選為簇頭，反之則不然。

LEACH協(xié)議中的簇頭每次都是隨機產(chǎn)生的，所以簇頭的位置會出現(xiàn)分配不均勻，對節(jié)約節(jié)點能量不利。另外，每個簇頭直接與基站節(jié)點通訊，這會導(dǎo)致距離基站遠(yuǎn)的節(jié)點能量提前耗盡，因而該協(xié)議均衡節(jié)點能耗的性能較差。

PEGASIS協(xié)議是對LEACH協(xié)議的改進(jìn)，核心思想是:采用貪婪算法，每個節(jié)點只和它的最近鄰居節(jié)點通信，節(jié)點輪流擔(dān)任Leader節(jié)點，負(fù)責(zé)與基站通信，當(dāng)所有節(jié)點都擔(dān)任過Leader節(jié)點以后，再進(jìn)行新一輪的通信。PEGASIS協(xié)議的這種輪流通信機制使得能量消耗統(tǒng)一分配到每個節(jié)點上，從而降低了整個傳輸過程的能量消耗。與LEACH協(xié)議相比，PEGASIS協(xié)議提高了近兩倍的生命周期。但是PEGASIS協(xié)議也有不足:網(wǎng)絡(luò)中每個節(jié)點都能直與基站通信，從而導(dǎo)致遠(yuǎn)端節(jié)點在擔(dān)任鏈的首節(jié)點期間要消耗相對較多的能量;PEGASIS協(xié)議節(jié)點具有相同的初始能量，因此可能在同一時間全部死亡;PEGASIS協(xié)議所構(gòu)造的鏈中，運用貪婪法經(jīng)常會引起長鏈，這也會導(dǎo)致長鏈兩端的節(jié)點能量消耗相對較大。

2 其他相關(guān)改進(jìn)算法

由于LEACH協(xié)議和PEGASIS協(xié)議存在的不足，國內(nèi)外學(xué)者對其進(jìn)行了改進(jìn)。LEACH協(xié)議的改進(jìn)算法有LEACH-C[6]協(xié)議等。PEGASIS協(xié)議的改進(jìn)算法有EEPB[7]算法和基于遺傳算法的無線傳感網(wǎng)PEGASIS算法的改進(jìn)[8]等。

LEACH-C協(xié)議對分簇的算法進(jìn)行了改進(jìn)，不再隨機選擇簇頭。它是一種集中式的分簇路由協(xié)議，在其每個周期的開始階段，所有節(jié)點把自己的位置信息和剩余能量值發(fā)往基站?；驹谑盏竭@些信息后，首先計算所有節(jié)點的平均能量值，把能量不低于平均能量值的節(jié)點作為候選節(jié)點。這種方式能夠減少選舉簇頭時因通信而消耗的能量，從而有更多的剩余能量用于傳輸數(shù)據(jù)。

EEPB協(xié)議通過引進(jìn)距離門限避免相鄰節(jié)點長鏈的產(chǎn)生。在選舉Leader節(jié)點時候，考慮了節(jié)點的剩余能量和節(jié)點到基站的距離值兩個參數(shù)?；谶z傳算法的無線傳感網(wǎng)PEGASIS算法的改進(jìn)在其鏈形成階段采用遺傳算法，減少了傳輸距離。此算法鑒于發(fā)送數(shù)據(jù)時消耗的能量與傳輸距離的平方成正比，盡可能形成一條距離的平方和最短的鏈，并根據(jù)節(jié)點的剩余能量進(jìn)行簇頭選擇。這兩種協(xié)議平衡了各節(jié)點的能耗，具有比PEGASIS協(xié)議更好的節(jié)能性。

3 交錯分鏈結(jié)構(gòu)的路由協(xié)議

基于LEACH協(xié)議和PEGASIS協(xié)議的分析，本文提出了一種改進(jìn)的路由協(xié)議:交錯分鏈結(jié)構(gòu)的路由協(xié)議。

網(wǎng)絡(luò)假設(shè):

(1)節(jié)點的發(fā)射功率可以動態(tài)調(diào)節(jié)，從而節(jié)省能量;

(2)網(wǎng)絡(luò)中的節(jié)點是同構(gòu)的，也就是具有相同的通訊能力以及數(shù)據(jù)處理能力，都有可能成Leader節(jié)點;

(3)所有節(jié)點都是靜止的，符合大多數(shù)的應(yīng)用環(huán)境;

(4)所有節(jié)點都有一跳和基站通信的能力。

(5)每個節(jié)點在網(wǎng)絡(luò)中有唯一的ID號，并且能夠感知自己的坐標(biāo)值。

3.1 鏈的劃分

網(wǎng)絡(luò)節(jié)點隨機分布以后，建立一個包含所有節(jié)點的網(wǎng)絡(luò)直角坐標(biāo)系。每個傳感器節(jié)點通過自己的坐標(biāo)值計算自己的橫鏈標(biāo)識號和縱鏈標(biāo)識號，計算公式如下:

Cluster_id_horizontal=ceil(y*p));

Cluster_id_row=ceil(x*p));

其中，Cluster_id_horizontal代表橫鏈的標(biāo)識號，Cluster_id_row表示縱鏈的標(biāo)識號。ceil表示將某個值向上取整數(shù)值。如:ceil(1.1)=2.p代表鏈數(shù)占節(jié)點總數(shù)的百分比，x和y代表節(jié)點的坐標(biāo)值。

3.2 Leader的選舉

整個網(wǎng)路中存在唯一的Leader，選舉的策略是剩余能量最大的節(jié)點作為Leader.首輪Leader隨機選舉，因為在第一輪的時候節(jié)點的能量都大致相同。由基站向整個網(wǎng)絡(luò)廣播Leader的信息。此后，由鏈端節(jié)點開始把自己剩余能量的消息告訴下一跳節(jié)點。這個過程采用信息捎帶技術(shù)，與采集的數(shù)據(jù)在同一數(shù)據(jù)包內(nèi)。下一跳傳感器節(jié)點收到該數(shù)據(jù)包以后，提取剩余能量部分的信息，與自己的剩余能量對比，把較大剩余能量的節(jié)點信息傳送給自己的下一跳節(jié)點。依此類推，最后把剩余能量最大的節(jié)點信息傳送給基站。

基站將采集的數(shù)據(jù)進(jìn)行處理，并提取網(wǎng)絡(luò)中剩余能量最大的節(jié)點信息，該節(jié)點將作為下一輪的Leader。然后，基站向整個網(wǎng)絡(luò)廣播該節(jié)點信息，開始新一輪的數(shù)據(jù)采集。

本文并沒有引進(jìn)距離作為選舉leader的參數(shù)。因為引進(jìn)距離參數(shù)以后，只會提前消耗距離基站較近節(jié)點的能量，實際意義不大，反而會增加算法復(fù)雜度。

3.3 節(jié)點成鏈

在第一輪成鏈的時候，需要先建立路由表。此時采用基站統(tǒng)一管理的方式:按照節(jié)點ID的大小順序，節(jié)點依次把自己的相關(guān)信息傳送給基站。該信息包括:節(jié)點的ID，坐標(biāo)值，橫鏈和縱鏈的標(biāo)識號?；臼盏剿泄?jié)點的數(shù)據(jù)信息后，進(jìn)行處理，得出每個節(jié)點的路由信息。每個路由信息包含橫鏈上的鄰居節(jié)點信息和縱鏈上的鄰居節(jié)點信息。然后，基站按照節(jié)點ID的大小順序，依次把路由信息發(fā)送給相應(yīng)節(jié)點，收到路由信息的節(jié)點建立路由表，并保存路由信息。

在基站廣播Leader節(jié)點的信息以后，每個節(jié)點查看自己的縱鏈標(biāo)識號，查看是否和Leader在同一縱鏈內(nèi)，如果縱鏈標(biāo)識號不同，只進(jìn)行橫鏈方向的數(shù)據(jù)傳輸。如果和Leader節(jié)點的縱鏈標(biāo)識號相同，就要進(jìn)行縱鏈方向的數(shù)據(jù)傳送，此外還要查看橫鏈上的鄰居節(jié)點是否和自己在同一縱鏈內(nèi)。如果橫鏈上的鄰居節(jié)點和自己在同一縱鏈上，只進(jìn)行縱鏈方向的傳輸，否則，還要接收來自該相鄰節(jié)點的數(shù)據(jù)信息。

在每輪開始的時候，每個節(jié)點根據(jù)Leader節(jié)點的信息分析自己數(shù)據(jù)的傳送方向以及應(yīng)該接收的數(shù)據(jù)包的數(shù)量。通過數(shù)據(jù)傳輸?shù)姆较蛞约皯?yīng)該接收的數(shù)據(jù)包數(shù)量，每個節(jié)點就可以計算出本輪的能量消耗。如果自己的剩余能量不足以承受，就廣播消息告知鄰居節(jié)點刷新相關(guān)的路由表，該節(jié)點就默認(rèn)為死亡。廣播消息的半徑是鄰居節(jié)點中最遠(yuǎn)節(jié)點的距離值。

根據(jù)路由表構(gòu)鏈的時候，如果發(fā)現(xiàn)某個節(jié)點的下一跳節(jié)點跳過了本輪Leader的縱鏈區(qū)域，該節(jié)點就要在Leader所在縱鏈上尋找一個距離最近的節(jié)點，并把采集的數(shù)據(jù)傳送給這個最近節(jié)點。

通過以上兩種方式，可以保證每次通信的過程中都不會出現(xiàn)盲點，發(fā)生斷鏈現(xiàn)象，同時避免了拓?fù)渲貥?gòu)。

在鏈結(jié)構(gòu)形成以后，整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如下圖1所示:圖中黑色實線代表網(wǎng)絡(luò)中節(jié)點之間形成的橫鏈，虛線線表示和Leader在同一縱鏈內(nèi)的節(jié)點形成的縱鏈，點線表示橫鏈和縱鏈之間的連接線，圈中帶*的節(jié)點表示Leader節(jié)點。

圖1 拓?fù)浣Y(jié)構(gòu)Fig.1 The structure of topology

3.4 網(wǎng)絡(luò)通信階段

整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)建立完成以后，節(jié)點根據(jù)自己的路由表可以查出是否是鏈端節(jié)點。鏈端節(jié)點首先開始傳送數(shù)據(jù)。節(jié)點在接收到來自鄰居節(jié)點的數(shù)據(jù)信息以后，查看是否所有數(shù)據(jù)都已經(jīng)接收完畢。當(dāng)接收完所有的信息以后，把相關(guān)的數(shù)據(jù)信息進(jìn)行數(shù)據(jù)融合，并傳給下一跳節(jié)點。最終把數(shù)據(jù)傳給Leader，再由Leader將數(shù)據(jù)傳給基站。

4 仿真過程及結(jié)果

在MATLAB上進(jìn)行仿真實驗，采用的能量模型如下:

其中，Esend為發(fā)送每位數(shù)據(jù)所消耗的能量，k為發(fā)送數(shù)據(jù)的長度，d是發(fā)送數(shù)據(jù)的距離，Efs表示傳送數(shù)據(jù)時能量消耗的系數(shù)，與數(shù)據(jù)長度和距離平方值相關(guān)。

當(dāng)接收數(shù)據(jù)時，模型如下:

其中EDA為數(shù)據(jù)融合時的能量消耗參數(shù)。ERX表示接收每位數(shù)據(jù)的能量消耗。

仿真環(huán)境:將100個節(jié)點隨機分布在整個正方區(qū)域內(nèi)，正方形區(qū)域的半徑為100 m，基站的位置坐標(biāo)是(50，300)，遠(yuǎn)離整個網(wǎng)絡(luò)，節(jié)點初始能量為0.25 J，數(shù)據(jù)包大小為2000 bits.表1是其他參數(shù)值的說明。

表1 仿真參數(shù)表Tab.1 The parameters of simulation

4.1 首節(jié)點死亡

以第一個節(jié)點死亡的時間作為網(wǎng)絡(luò)的生命周期[9]，分別對三種路由協(xié)議進(jìn)行了仿真實驗，得出三種路由協(xié)議的實驗結(jié)果，參數(shù)對比如圖2.

圖2 能耗對比圖Fig.2 The comparison of energy consumption

從圖中的可以看出:LEACH協(xié)議的網(wǎng)絡(luò)壽命為180輪，PEGASIS協(xié)議的網(wǎng)絡(luò)壽命為330輪，而交錯分鏈結(jié)構(gòu)路由協(xié)議的網(wǎng)絡(luò)壽命為800輪。因此，交錯分鏈結(jié)構(gòu)路由協(xié)議大大提高了網(wǎng)絡(luò)的壽命。

4.2 剩余總能量和運行輪數(shù)的關(guān)系

剩余總能量和運行輪數(shù)的關(guān)系如圖3所示。

圖3 剩余能量與運行輪數(shù)的關(guān)系Fig.3 The relation of residual energy and rounds

隨著數(shù)據(jù)的傳輸輪數(shù)的增多，每個節(jié)點的剩余能量不斷減少，總的剩余能量也隨之減少。LEACH協(xié)議中的節(jié)點總剩余能量在340輪左右消耗殆盡，此時交錯分鏈結(jié)構(gòu)路由協(xié)議的總能量消耗了大約40%.PEGASIS協(xié)議的能量消耗比LEACH要好，但是差于分鏈結(jié)構(gòu)路由協(xié)議，在不到760輪的時候全部死亡，交錯分鏈結(jié)構(gòu)路由協(xié)議全部死亡大約在850輪。

4.3 分鏈數(shù)目的影響

本文把整個網(wǎng)絡(luò)分為五個橫鏈，是實驗后得出的結(jié)果。本文分別對 2、4、5、7、9五種不同的鏈數(shù)進(jìn)行了仿真實驗，得出圖4的對比圖。

圖4 不同分鏈數(shù)量的對比Fig.4 The comparison of different partition － chain amount

由圖4可以看出:當(dāng)分為五個鏈的時候，首節(jié)點的死亡時間達(dá)到最大運行輪數(shù)，隨著鏈數(shù)值的增大或減小，這個數(shù)值都會逐漸減小。所以，當(dāng)鏈數(shù)值為5的時候，本協(xié)議的性能最好。

在實驗的結(jié)果中還得出表2的數(shù)據(jù)，表中p表示鏈數(shù)與網(wǎng)絡(luò)節(jié)點總數(shù)的比值。例如:節(jié)點總數(shù)為100，當(dāng)p=0.02，就表示分為兩個鏈。通過表2可知當(dāng)p=0.05的時候，無論是是首節(jié)點死亡時間，還是節(jié)點全部死亡的時間，網(wǎng)絡(luò)都能達(dá)到最好的性能。

表2 不同分鏈數(shù)的性能對比Tab.2 The performances of different amount of chain

5 結(jié)束語

交錯分鏈結(jié)構(gòu)路由協(xié)議改進(jìn)了LEACH協(xié)議的簇分配不均等問題，也改進(jìn)了PEGASIS協(xié)議中存在的長鏈現(xiàn)象。交錯分鏈結(jié)構(gòu)路由協(xié)議拓?fù)浣Y(jié)構(gòu)形成以后，就不會改變，不像LEACH協(xié)議，需要不斷的改變拓?fù)浣Y(jié)構(gòu)。PEGASIS協(xié)議在有節(jié)點出現(xiàn)死亡的時候，需要重構(gòu)網(wǎng)絡(luò)，這樣在網(wǎng)絡(luò)后期有大量節(jié)點死亡的時候，將會不斷地進(jìn)行拓?fù)渲貥?gòu)。交錯分鏈結(jié)構(gòu)路由協(xié)議只需要刷新相關(guān)節(jié)點的路由表，跳過死亡節(jié)點，因此節(jié)省了網(wǎng)絡(luò)拓?fù)渲貥?gòu)消耗的能量。另外，本協(xié)議的Leader選舉策略與PEGASIS協(xié)議相比，在均衡網(wǎng)絡(luò)中節(jié)點能耗的方面性能更好。

總之，交錯分鏈結(jié)構(gòu)的路由協(xié)議與LEACH協(xié)議和PEGASIS協(xié)議相比，在能量負(fù)載平衡和網(wǎng)絡(luò)的生命周期方面都有很大的提高。

[1]REN FENG-YUAN，HUANG HAINING，LIN HUANG.Wireless Sensor Network[J].Journal of Software，2003，4(7):1282-1291.

[2]LAN F AKYILDIZ，SU WEILIAN，YOGESH SANKARASUBRAMANIAM，et al.A Survey on Sensor Networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[3]張治中，曾建潮.基于PSO的無線傳感器網(wǎng)絡(luò)自組織成簇算法[J].太原科技大學(xué)學(xué)報，2009，30(6):484-489.

[4]宋文，王兵，周應(yīng)兵.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京:電子工業(yè)出版社，2007:2-3.

[5]WENDI RABINER HEINZELMAN，ANANTHA CHANDRAKASAN，HARI BALAKRISHNAN.Energy-Efficient Communication Protoclo for Wireless Microsensor Networks[C]//Proceedings of the 33rdHawaii International Conference on System Sciences，USA，Hawaii，2000.

[6]LINDSEY S，RAGHAVENDRA C.PEGASIS:Power-efficient gathering in sensor information[C]//IEEE Aerospace Conference Proceedings，SanFrancisco:IEEE Computer Society，2002.1125-1130.

[7]HEINZELMAN W，CHANDRAKASAN A，BALAKRISNAN H.An applicationspecific protocol architecture for wireless microsensor networks[J].IEEE Transaction on Wireless Communications，2002，1(4):660-670.

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

[9]胡森來，張昱，金心宇，等.基于遺傳算法的無線傳感網(wǎng)的PEGASIS協(xié)議的改進(jìn)[J].江南大學(xué)學(xué)報(自然科學(xué)版)，2008，7(4):420-424.

[10]田瑩，王瑩，張淑芳.高效節(jié)能的鏈?zhǔn)椒謱訜o線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計算機工程與應(yīng)用，2007，43(35):22-26.