長距離帶狀無線傳感器網絡路由協議設計

王 偉

?

長距離帶狀無線傳感器網絡路由協議設計

王 偉

(中煤科工集團沈陽研究院有限公司，遼寧 撫順 113122)

帶狀網絡的長帶狀特性會影響無線傳感器網絡路由協議的性能，導致網絡出現“熱區”。針對該問題，提出一種能量均衡的多跳路由協議CRLDB。該協議主要采用非均勻分簇的思想，引入備選簇首競爭半徑的概念和相應的競爭策略，并加入最優簇首個數、節點剩余能量和周圍鄰居節點個數的簇首選擇機制，使節點的剩余能量和傳輸能量達到平衡。NS2仿真實驗結果證明，與LEACH和LEACH-C協議相比，CRLDB在網絡的生存時間、整體能耗和基站收到的數據量這3個性能指標上有較大程度的提高，能更好地均衡網絡的能量消耗，提高網絡的生命周期。

無線傳感器網絡；分簇；長距離帶狀網絡；路由協議；CRLDB協議；簇首

1 概述

無線傳感器網絡(Wireless Sensor Network, WSN)[1]由大量的傳感器節點組成，節點通過本身的各種傳感器采集數據，通過無線通信的方式，傳遞信息到目的地，共同完成某一目標的智能型無線網絡。無線傳感器網絡是計算機科學技術的一個重要研究領域，受到學術界和工業界的高度重視，對人類的社會生活和工業變革造成巨大的影響[2]。

WSN節點具有能量有限的特點，因此，WSN路由協議一直是研究的熱點，如何提高網絡的生命周期成為其主要目標[3]。在以往的研究中，已經有很多種路由協議，如定向擴散協議DD(Directed Diffusion)[4]、自適應路由協議SPIN (Sensor Protocol for Information via Negotiation)[5]、低功耗自適應聚類路由協議LEACH(Low Energy Adaptive Clustering Hierarchy)[6]、能量高效的路由協議TEEN(Threshold sensitiveEnergy Efficient sensor Network protocol)[7]、PEGASIS(Power- efficient Gathering in Sensor Information Systems)[8]等協議。文獻[9]提出了一種能量高效均衡的分布式分簇路由協議DEBUC(Distributed Energy-balanced Unequal Clustering routing protocol)，采用貪婪算法在鄰居簇頭集合中選擇其中繼節點，達到延長網絡生存周期的目的。文獻[10]提出了一種基于雙簇頭交替和壓縮感知的WSN路由協議DCHACS (Double Cluster Head Alternation and Compressed Sensing)，采用雙簇頭交替機制分擔簇頭的負擔，簇頭節點利用壓縮感知理論進行數據融合。文獻[11]提出了以非均勻分簇的思想來均衡簇頭節點能耗，簇間采用多跳方式，簇內通信能耗和成員節點數量成比例關系，使得所有簇頭的能耗接近，網絡能量消耗均衡。

但在特定環境中，如長距離的街道、帶狀的峽谷、長帶狀河流、跨江大橋、高速公路、井下巷道等環境，無線傳感器網絡需要布置成狹長的帶狀結構。對于這種特殊的長帶狀網絡，傳統的WSN路由協議在此場景下存在局限性，因此，本文設計長帶狀網絡條件下能量均衡的路由協議，協議中采用分簇的結構，通過大小不等的簇的結構提高網絡的性能。

2 一種能量均衡的多跳路由協議

本文研究的網絡拓撲結構為長距離帶狀，主要應用在河流、跨江大橋、煤礦巷道等特殊環境。因此，本文設計一種長距離帶狀網絡環境下的分簇路由協議(Cluster- based Routing in Long Distance Band-type network, CRLDB)。CRLDB協議也是基于分簇的路由協議，但不同于LEACH，由于網絡呈長帶狀分布，若采用單跳路由形式，距離匯聚節點遠的節點能量很容易耗盡。一般來說，通過動態分簇的形式可以大大地減小網絡的負載，把能量的消耗平均在整個網絡的所有節點上，這樣就可以提高網絡的有效性，盡可能減少節點死亡的概率，提高網絡的生命周期。CRLDB協議采用多跳的形式，以動態的方式進行簇首的簇首選舉，簇首一旦確定，網絡內的簇結構便建立起來。當網絡呈長帶狀分布時，信息流一般向一側流向匯聚節點，假設數據融合量很小，這樣數據流就會呈“棒槌”狀，越靠近匯聚節點數據量越大，造成的“熱區”問題更為嚴重。故本文的核心思想是利用非均勻分簇，越靠近匯聚節點簇的規模越小，來解決“熱區”問題，平衡整個網絡的負載，提高網絡的生存時間達到增加網絡壽命的目的。

2.1 基本網絡模型

為了更有利于協議的研究，本文給出如下假定：

(1)傳感器網絡由個普通傳感器節點和1個匯聚節點(由Sink表示，也可以叫基站)組成，其中普通節點具有相同的計算、通信能力和初始能量水平，而匯聚節點的能量和計算能力是沒有限制的。

(2)匯聚節點位于帶狀網絡的一端，網絡部署完畢后，所有節點(包括Sink節點)都是靜止不動的。

(3)傳感器節點具有全網唯一的ID，同時鏈路是對稱的，若已知對方發射功率，節點可以根據接收信號的強度計算出發送者到自己的近似距離。

(4)節點可調整自己的無線電發射功率，也就是節點可根據通信距離長短來調整發射功率的大小。

2.2 能量傳輸模型

本文采用與文獻[12]相同的無線能量模型，發送節點和接收節點之間的距離小于0時，采用自由空間模型，發射功率呈2衰減；否則采用多路徑衰減模型，發射功率呈4衰減，能量消耗定義如下：

2.3 簇首選取策略

2.4 非均勻簇的建立

在網絡部署階段，基站節點以一個固定的發送功率向全網內廣播一個Hello信號。每個傳感器節點在接收到這個信號后，根據接收信號的強度來計算它到基站的近似距離n。這個距離n在本文非均勻分簇中用來計算簇的半徑的必要參數。一旦某個節點通過上面的簇首選擇公式計算成為備選簇首節點，就可以根據下面的計算公式來算出備選簇首的覆蓋半徑半徑e的大小。

備選簇首半徑e的計算公式如下：

其中，1、2是普通參數，0<1、2<1，且有1+2=1，max是網絡中所有節點與Sink節點距離的最大值，min是網絡中的所有節點到Sink節點的最小值，0為簇的最大半徑。

當簇首節點距離基站最遠時，且當前節點剩余能量等于初始能量時，=max、cur=int，有e=0，此時簇的范圍最大。隨著節點與基站距離的減小，簇首的剩余能量的降低，簇的覆蓋范圍隨之也變小，當簇首距離基站最近時，=min，e=20cur/int，式中只有cur為變量，因此，此時簇的覆蓋范圍隨著節點的剩余能量的減少而逐漸降低。 同時也考慮節點剩余能量的狀況，節點的剩余能量越高，它的覆蓋半徑越大；反之，節點的剩余能量越低，它的覆蓋半徑越小，這樣它傳輸的距離就相對較小，更能節約能量。備用簇首的覆蓋半徑如圖1所示。

圖1 備選簇首非均勻分簇效果

定義1(競爭半徑) 本文定義備選簇首的參數e的大小為競爭半徑。

定義2(簇首的競爭規則) 在競選過程中，若某個備選簇首成功當選，則在它的競爭半徑范圍內的所有其他備選簇首都退出，從而轉變成普通節點。

圖2給出了一張由4個備選簇首組成的拓撲結構圖，其中1、2、3、4為備選簇首節點。由上面的規則得出，3和4可以同時成為最終簇首，而1和2則不能同時成為最終簇首，因為2位于1的競爭區域內部，因此，只有1、3、4成為最終簇首，而2轉變為普通節點。

圖2 備選簇首的競爭過程

2.5 簇間數據傳輸策略

算法的主要步驟如下：

當一個簇首節點(假設為簇首節點)想要發送數據包給基站時：

(1)選擇能量參數()，()包含2個部分：

2)中間節點本身的剩余能量，參數()計算式如下：

其中，AX是節點到未知節點的距離；X?BS是未知節點到基站(BS)的距離，resX是未知節點的剩余能量。集合S為簇首節點下一跳路由的所有可能的簇首節點。集合S的定義如下：節點N經過多跳路由傳送數據包到基站時，下一條路由節點N的集合S為：

(2)從上式中可以得知，當cur=int且d=min時，簇首e的半徑為最大值，即emax=0。所以簇首A以半徑為20向集合S中的簇首發送自己的ID路由信息，接收簇首在本地計算()，反饋給簇首。

(3)簇首A得到反饋數據后比較()，選擇使()值最小的節點X，即min()。若通過計算發現未知節點X是節點的話，那么就直接把數據傳給基站。否則，選擇未知節點(這里假設節點)作為傳輸到基站的一個中間節點。

(4)如果節點被選作中間節點并從簇首節點A收到數據包的話，接下來簇首節點按式(5)繼續尋找一個跳的簇首節點。

(5)重復步驟(1)~步驟(4)，直到數據傳輸給基站為止。

2.6 CRLDB路由協議的具體過程

CRLDB路由協議的具體過程如下：

階段1網絡部署

在開始階段，讓基站以一定的功率向整個網絡廣播一個消息Information_MSG。傳感器節點根據接收信號的強弱估算出自己到基站的近似距離d，在與基站通信時，依據這個距離選擇適當的發射功率。在成簇階段，還將利用這個信息來均衡簇首的負載。

階段2簇頭選舉

根據預先一個設定好的0~1之間的閾值new()，用來控制參加簇首競選的節點比例。每一個節點生成一個0~1之間的隨機數，記為。若new()，則該節點成為簇頭備選節點，然后每個備選節點延遲時間后，在競爭半徑內廣播一個競選消息COMPETE_HEAD，內容為自身標識符。只有在半徑覆蓋范圍內的備選節點才能接收到此消息。若有備選節點N接收到備選節點N廣播的消息后，則N立即放棄競選，變成普通節點。一定時間后，競選消息在網絡內傳播結束，表明該階段完成。剩余的備選節點則成為此輪選舉產生的簇首。

階段3簇類形成

簇首在競爭半徑內廣播自己成為簇首的消息HEAD_AD，普通節點接收到此消息后，加入這個簇首所在的簇，最終形成一個個簇類。

階段4 數據傳輸

簇首頭向所有成員節點廣播TDMA通信時隙調度信息TDMA_SCHEDULE。成員節點按分配好的TDMA時隙在某個時刻將自己檢測到的數據發送給簇首。簇首在接收聚類成員發送數據的過程中進行數據融合后，尋找下一跳路由的路徑，規則是在集合S中尋找一個使()最小的簇首節點作為下一跳路由。以此類推，最后形成從簇首到基站的一條或條近似鏈狀的路。

圖3給出了CRLDB路由協議每一輪算法的流程。

圖3 CRLDB路由協議算法流程

3 實驗及結果分析

3.1 最優簇首個數Kopt的確定

在上文中提及最優簇首opt的計算公式為：

可見最優簇首Kopt和節點的個數、節點到基站的距離等參數有關。場景1和場景2節點與基站的距離分別為：75

圖5 簇首個數與網絡運行時間關系(場景2)

3.2 網絡的生命周期

圖6和圖7是場景1和場景2中網絡運行時間與存活節點個數的關系。可以看出，LEACH、LEACH-C、CRLDB 3種路由協議隨著網絡的運行時間的增加，在開始一段時間之后，網絡的節點開始逐漸死亡，直到所有的節點全部死亡為止。同時可以看出，LEACH、LEACH-C的性能相互相近，但LEACH-C的性能比LEACH更好。

圖6 3種路由協議網絡運行時間與存活節點個數的關系(場景1)

圖7 3種路由協議網絡運行時間與存活節點個數的關系(場景2)

3.3 網絡的總體能耗

圖8與圖9分別給出了在2種場景下，隨著網絡運行時間的變化網絡所消耗的能量的變化關系。從圖中可以看出，在場景1中，LEACH、LEACH-C協議約在網絡運行570 s左右時網絡的能量被耗盡，而CRLDB協議在整體能量被耗盡時網絡運行了超過800 s，性能提高了約40%。在場景2中，當網絡中能量被耗盡時，CRLDB協議運行時間分別比LEACH、LEACH-C提高了61%和41%。從而看出，當網絡規模變大時，CRLDB的性能更加顯著。

圖8 3種協議網絡運行時間與網絡消耗總能量的關系(場景1)

圖9 3種協議網絡運行時間與網絡消耗總能量的關系(場景2)

4 結束語

本文通過對長距離帶狀網絡的分析，提出一種基于非均勻分簇的路由協議CRLDB，并介紹相關算法。通過仿真證明，CRLDB協議能改善由“熱區”效應帶來的能量消耗不均衡的問題。今后的主要研究方向是在特殊網絡或者特定環境下對WSN路由協議進行改進，延長網絡生命周期。

[1] 于海斌, 曾 鵬. 智能無線傳感器網絡系統[M]. 北京: 科學出版社, 2006.

[2] Karl H, Willim A. Protocols and Architectures for Wireless Sensor Networks[M]. 丘天爽, 譯. 北京: 電子工業出版社, 2007.

[3] 路 綱, 周明天, 佘 堃, 等. 無線傳感器網絡路由協議的壽命分析[J]. 軟件學報, 2009, 20(2): 375-393.

[4] Intanagonwiwat C, Govindan R, Estrin D, et al. Directed Diffusion for Wireless Sensor Networking[J]. IEEE/ACM Transactions on Networking, 2003, 11(1): 2-16.

[5] Kulik J, Heinzelman W, Balakrishnan H. Negotiation Based Protocols for Disseminating Information in Wireless Sensor Networks[J]. Wireless Networks, 2002, 8(2/3): 169-185.

[6] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy- efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc. of the 33rd Annual Hawii International Conference on System Sciences. Maui, USA: IEEE Computer Society, 2000: 1-10.

[7] Manjeshwar A, Agrawal D. TEEN: A Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]//Proc. of the 15th IEEE International Parallel and Distributed Processing Sym- posium. Hawaii, USA: IEEE Computer Society, 2001: 23-27.

[8] Lindsey S, Raghavendra C S. PEGASIS: Power-efficient Gathering in Sensor Information Systems[C]//Proc. of IEEE Aerospace Conference. San Francisco, USA: IEEE Computer Society, 2002: 1-6.

[9] 蔣暢江, 石為人, 唐賢倫, 等. 能量均衡的無線傳感器網絡非均勻分簇路由協議[J]. 軟件學報, 2012, 23(5): 1222-1232.

[10] 趙小川, 周 正, 秦智超. 基于雙簇頭交替和壓縮感知的WSN路由協議[J]. 軟件學報, 2012, 23(1): 17-24.

[11] Soro S, Heinzelman W B. Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering[C]//Proc. of the 19th IEEE International Parallel and Distributed Processing Symposium. Denver, USA: IEEE Computer Society Press, 2005: 4-8.

[12] Shepard T. A Channel Access Scheme for Large Dense Packet Radio Networks[C]//Proc. of ACM SIGCOMM. Cambridge, USA: Association for Computing Machinery, 1996: 1-12.

編輯 金胡考

Design of Routing Protocol in Long Distance Band-type Wireless Sensor Network

WANG Wei

(CCTEG Shenyang Engineering Co., Ltd., Fushun 113122, China)

Aiming at the problem that characteristics of the long distance band-type network will constrain the effect of general Wireless Sensor Network(WSN) routing protocols, and causes a “hot spot” problem in long distance band-type network, this paper introduces the energy balanced consumption multi-hop routing protocol CRLDB. It takes the idea of non-uniform cluster, concept of competition radius and the corresponding competitive strategy, and joins the number of cluster head node selection mechanism with the optimal number of cluster head, node residual energy and the surrounding neighbors, to balance nodes residual energy and transmission energy. Simulation by NS2 shows CRLDB routing protocol, compared with existing routing protocols Low Energy Adaptive Clustering Hierarchy(LEACH), LEACH-C for the survival time in the network, the network’s overall energy consumption and the amount of data received by base stations, CRLDB protocol with several performances in the above has a large improvement, can balance the network’s energy consumption and increase the network’s lifetime.

Wireless Sensor Network(WSN); clustering; long distance band-type network; routing protocol; CRLDB protocol; cluster header

1000-3428(2014)03-0132-05

A

TP393

王 偉(1984－)，男，助理工程師、碩士，主研方向：無線傳感器網絡。

2012-12-14

2013-03-21 E-mail：forrestwang113@gamil.com

10.3969/j.issn.1000-3428.2014.03.027