一種無線自組網均勻分布簇結構路由
2008-12-31 00:00:00胡福林肖海軍
計算機應用研究 2008年11期
(華中科技大學 計算機科學與技術學院， 武漢 430074)
摘要：在低能量自適應簇結構層次(low-energy adaptive clustering hierarchy，LEACH)路由協議的基礎上，提出了一種均勻的分布式簇結構層次路由協議。該協議將路由過程分為三個步驟，按照能量均衡的原則選取簇頭節點，各節點能夠分布式地自主決定該節點的狀態。仿真結果顯示，該協議擁有比LEACH更低的能量消耗和更長的網絡生命周期。
關鍵詞：均勻分布；簇結構路由；能量有效
中圖分類號：TP393文獻標志碼：A
文章編號：1001-3695(2008)11-3412-03
Equally distributed clustering routing in wireless self organized networks
HU Fu-lin，XIAO Hai-jun
（College of Computer Science Technology， Huazhong University of Science Technology， Wuhan 430074， China）
Abstract:This paper proposed an equally distributed clustering hierarchy routing protocol(EDCHR) which basing on the low-energy adaptive clustering hierarchy routing protocol(LEACH).EDCHR divided the routing protocol into three steps. Each node could decide its state by itself. The cluster header was selected according to energy uniform principle. The simulation result shows that EDCHR has lower energy assumption and longer network lifetime.
Key words:equally distributed; clustering hierarchy routing protocol; energy efficient
隨著競爭的加劇，企業越來越希望他的員工在離開辦公室時，仍能通過基于一個號碼上的綜合通信服務，隨時隨地利用公司的語音與數據網絡資源移動辦公，提高辦公效率，降低通信費用。企業這種移動辦公的需求，對通信運營商、設備制造商提出了挑戰——需要使用移動自組織網絡，滿足企業用戶高效、便捷、靈活、經濟的個性化通信需求[1，2]。
與傳統的通信網絡相比，移動自組織網絡具有自組織、網絡拓撲動態變化、多跳路由和節點能量受限等特點。其中，最大的限制因素是在移動辦公的環境下，網絡中各節點所在的工作環境可能在短時間內無法補充到能量，所以在移動自組織網絡路由協議的設計過程中，必須充分地考慮節點的能量消耗問題[3]。為了達到高效使用能量和延長網絡生命周期的目的，使用簇結構來組織各個節點。簇成員節點(cluster member，CM)將收集到的信息發送到簇頭節點(cluster header，CH)，由簇頭節點進行數據融合并將融合后的信息發送到基站(base station，BS)。在自組織網絡的簇結構形成過程中，如何選擇簇頭，各簇成員節點如何選擇所在的簇是非常關鍵的問題。特別是在網絡規模大時，簇結構對節能的作用將更加顯著[4，5]。
現階段已經提出了一些路由協議。LEACH路由協議[6]是一種基于簇結構的分布式路由協議。其中每個節點都可能被選為簇頭；剩余的節點將加入需要最小傳輸能量的簇中。基于LEACH協議，本文提出了一種均勻分布的簇結構層次路由協議(EDCHR)。該協議按照能量均衡的原則選取簇頭節點。仿真結果顯示，整個網絡擁有更長的生命周期。
1設計前提
11能量模型
使用文獻[7]中相同的能量模型如圖1所示。在該模型中，無線發送和接收的能量消耗為Eelec；εfs和εamp為信號放大的能量損失率。信道可使用最小能量消耗來發送數據或接收需要的數據，并且可以在不需要接收消息時關閉。
ETx=k×Eelec+k×εfsd2d＜d0
k×Eelec+k×εampd4d≥d0(1)
ERx=k×Eelec(2)
式(1)和(2)用來計算傳輸和接收k bit報文的負載。其中d是傳輸距離。當d＜d0時，信道遵循的是自由空間模型；否則，信道遵循多路徑衰退模型[7]。
12設計目標
本文的目標是在保證盡量小的能量消耗的情況下，保證自組織網絡中每個節點的能量均勻消耗。主要是：a)更低的能量消耗。節點相互通信的過程中，每個節點盡量遵循自由空間模型。在本文中，節點的通信范圍為r(也稱為簇半徑)。對于每個簇，其半徑應小于d0/2。如此可以保證任意兩個簇頭之間的距離小于d0。b)協議是完全分布式的。通過本地信息，每個節點可以決定自身的狀態。如此可以保證協議的可擴展性。如果協議要求節點知道全局信息，那么協議擴展時負載是非常大的，而且很難保證全局的信息一致性。c)簇頭節點在區域中均勻分布，以避免不必要的能量消耗。
13假設
1)除了基站，在簇形成的過程中，每個節點有相同的傳輸范圍。
2)對稱通信。例如，如果節點A可以接收到B發送的報文，那么節點B也一定可以接收到A發送的報文。
3)每個節點的位置信息是未知的。
2協議描述
為了方便描述，本文符號定義如表1所示。
表1符號定義表
符號含義
Ecur節點的當前能量
ET節點能量門限值
Pini節點可以成為后選簇頭節點的概率
Scan在節點傳輸半徑r范圍內，宣稱為后選簇頭節點的集合
Send在節點傳輸半徑r范圍內，宣稱為簇頭節點的集合
Sweight簇頭集合，其中記錄格式為[ID，Wd]
random隨機數
distanceBS節點到基站之間的距離
MAPK表示節點根據剩余能量，在競標簇頭節點時的標價
Wc權值，與簇頭節點和簇成員節點距離成反比
Wd權值，與簇頭節點和基站之間的距離成反比，Wd=1/distanceBS
本文將協議分為三個階段：
a)簇構造。在此階段中，每個節點都有一定的幾率成為簇頭節點。簇頭將在整個網絡中均勻地選取，并且每個簇頭會選擇一個特定的CDMA碼，用于簇之間的通信。當簇頭節點選舉出來后，每個簇成員節點選擇合適的簇頭。簇頭為簇成員節點選擇相應的TDMA時隙。
b)建立簇頭樹。為了節省簇頭節點之間通信的能量損失，EDCHR協議按照與基站的距離大小將簇頭組成簇頭樹。
c)傳送數據。簇成員節點收集所需數據，并周期性地將數據發往簇頭節點。簇頭融合接收到的數據，并通過簇頭樹將數據發送到基站。
21簇構造
在EDCHR協議中，簇構造階段有六步。從第一步到第四步是確定哪些節點為簇頭，而第五步和第六步是簇成員節點選擇簇頭。然后每個簇頭節點在簇間選擇特定的CDMA碼，為簇內各成員節點指定TDMA時隙。
在第一步中，各個節點產生一個隨機數。如果隨機數小于Pini，節點廣播CANDIDATE報文。報文包含節點ID和MARK，表明這些節點為后選簇頭節點。在將該報文發送到其鄰居節點的同時，記錄ID和MARK到Scan中。當鄰居節點收到CANDIDATE報文后，也記錄ID和MARK到其本身的Scan中。在一些特定的環境中，一些節點的Scan為空，也就是說該節點周圍沒有任何節點宣稱為后選簇頭節點。在第二步中，這些為空的節點將廣播CANDIDATE報文，宣稱本節點為后選簇頭節點。經過這兩步以后，每個節點的Scan為非空。第三步，每個節點選擇其Scan中MARK最大者為簇頭節點。如果該節點就是簇頭節點，它將廣播HEAD報文。報文包含節點ID，表明該節點宣稱為簇頭節點。如此可能產生依賴鏈，如圖2所示。
節點A認為自己是最大的MARK節點，而節點B認為是C，那么節點C將會廣播HEAD報文，并在Send中記錄。而節點B接收到HEAD報文后，肯定不會再發送HEAD報文，則節點A不會收到HEAD報文。所以可能產生有些節點Send為空的情況。第四步，如果節點沒有接收到任何HEAD報文(包括自身發送的)，那么它將廣播HEAD報文。集合Send的記錄中包含三個部分： 發送者ID、能量和權值Wc。
第一到第四步，選舉出簇頭。第五步，普通節點將會通過權值來判斷，并向權值最大的簇頭節點發送JOIN報文。簇頭節點將創建簇成員列表，并在收到普通節點JOIN報文后，將該節點加入到成員列表。第六步，簇頭選擇簇間通信的CDMA碼和簇內通信的簇成員TDMA時隙。
當節點的能量低于門限值時， EDCHR協議認為該節點死亡，從網絡中退出。偽代碼如下：
22創建簇頭樹
簇構造完成之后將要創建簇頭樹。首先，基站向全網廣播，各個簇頭節點接收到廣播以后，通過接收信號的強度獲得權值Wd。該權值反映了各簇頭節點與基站之間的距離。然后，每個簇頭以2r的通信半徑廣播WEIGHT報文。如果簇頭接收到WEIGHT報文，將儲存報文發送節點ID以及權值Wd。當所有的簇頭節點都廣播完WEIGHT報文后，各簇頭將選擇鄰近范圍內具有最大Wd的簇頭節點作為其父節點。如果擁有兩個權值相同的節點，選擇ID較大的作為父節點。最后，距離基站最近的簇頭將成為簇頭樹的根節點，并直接與基站通信。
當存活的簇頭越來越少時，簇頭之間將無法組成簇頭數。在這種情況下，所有的簇頭直接向基站發送數據報文。
23發送數據
在無線自組織網絡中，每個節點收集數據并在分配的時隙內將數據發送給簇頭。為了使得能量消耗最小化，每個簇成員只是在所分配的時隙才激活通信信道，而其他時間信道處于睡眠狀態。簇頭將每輪簇成員發送的消息收集起來，進行數據融合后，再轉發至基站。而EDCHR的設計中保證了2r＜d0，幾乎所有的通信都是遵循自由空間模型的，因此節省了大量的能量。
3仿真
本文中將LEACH、LEACH-C和EDCHR進行了仿真與比較。實驗平臺為Pentium 4 1.8 GHz，512 MB RAM，使用的操作系統是Windows 2000下的Cygwin平臺，網絡仿真平臺是NS227(network simulator version2.27)。第一個仿真場景，100個節點隨機分布在面積大小為500 m×500 m的區域，其中基站位置(50 m，100 m)。第二個仿真場景，100個節點隨機分布在面積大小為1 000 m×1 000 m的區域，其中基站位置(50 m，175 m)。每個節點初始能量為20 J。一旦節點死亡，將退出網絡。MAC層使用的802.11協議，模擬時間為200 s，每10 s一輪。
在LEACH和LEACH-C中，節點的傳輸半徑是隨著簇頭與基站的距離而變化的。EDCHR協議中，各個節點使用相同的傳輸半徑150 m，該距離與前兩種協議中節點的平均距離是比較接近的。圖3和4分別顯示了在500 m×500 m和1 000 m×1 000 m的環境下，存活節點數量的變化。由于EDCHR與前兩種協議節點間距離比較接近，開始的時候三種協議的性能比較接近。170 s以后，EDCHR的性能開始明顯優于LEACH和LEACH-C。可以看出EDCHR有著更長的生命周期，如圖3所示。
在1 000 m×1 000 m區域中，顯然，EDCHR的性能要優于前兩者。因為隨著網絡區域的增加，相同數量的節點在網絡中的分布將越來越稀疏。LEACH和LEACH-C協議中，通信的能量是隨著節點之間的距離增大而增加的。而EDCHR協議中，通信能量基本上是保持不變的，所以隨著網絡區域變大，EDCHR的網絡有著更大的生命周期，如圖4所示。
圖5和6中顯示的是500 m×500 m和1 000 m×1 000 m兩種場景中的節點總能量消耗情況。圖5中可以看到，LEACH的總能量消耗增長速度遠遠高于EDCHR，但是LEACH-C在30~90 s的總能量消耗是低于EDCHR的。這是因為EDCHR的簇構造以及簇頭樹的形成需要消耗一定的能量，但90 s以后，EDCHR的總能量消耗是最小的。圖6中，在170 s以后，EDCHR的總能量消耗高于LEACH和LEACH-C。這是因為仿真中，當剩余節點無法構成網絡的情況下，將終止仿真。EDCHR能夠保證節點均勻地消耗能量，所以仿真終止時的節點數更少。這意味著有更多的節點能量耗盡，所以EDCHR的總能量消耗較高。
圖7顯示簇構造和組成簇頭樹的能量消耗。在此階段，EDCHR在場景500 m×500 m和1 000 m×1 000 m中分別消耗了總能量的0.8%和3%，而LEACH和LEACH-C在相應的場景中大概只需要消耗總能量的0.5%和2%。這說明EDCHR在簇構成階段和組成簇頭樹階段的多次廣播消息還是需要消耗一定能量的。不過基于輪的簇協議每輪中間隔的時間比較長，所以這樣的大能量消耗并不是非常頻繁。從前面的結果中也可以看到，總的能量消耗，EDCHR還是優于LEACH和LEACH-C的。
由以上的分析可以得出如下結論：EDCHR有著更均勻的節點能量消耗、更少的總能量消耗和更長的網絡生命周期。
4結束語
本文針對無線移動自組織網絡能量受限、節點隨機分布的特點，提出一種均勻分布的簇結構層次路由協議(EDCHR)，使得自組織網絡能更好地滿足移動辦公的需求。其主要將路由協議分為三個步驟：隨機均勻地選擇簇頭、組成簇頭樹和數據傳輸以及融合。并用偽代碼描述了其中選擇簇頭和組成簇頭樹的過程。仿真結果顯示，EDCHR協議比LEACH、LEACH-C協議有著更加均勻的節點能量消耗，網絡中同期的總能量消耗更少，網絡中各節點有著更接近且更長的生命周期。
參考文獻：
［1］POTTIE G J，KAISER W J.Wireless integrated network sensors[J].Communications of the ACM，2000，43(5):51-58.
[2]HEINZELMAN W R.Application-specific protocol architectures for wireless networks[D].[S.l.]:Massachusetts Institute of Technology，2000.
[3]DUARTE-MELO E J，LIU Ming-yan.Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks[C]//Proc of Global Telecommunications Conference.2002:21-25.
[4]MHATRE V，ROSENBERG C.Homogeneous vs heterogeneous clustered sensor networks:a comparative study[C]//Proc of IEEE International Conference on Communications.2004.
[5]MHATRE V，ROSENBERG C，KOFMAN D，et al.A minimum cost heterogeneous sensor network with a lifetime constraint[J].IEEE Trans on Mobile Computing，2005，4(1): 4-15.
[6]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Annual Hawaii Int’l Conf on System Sciences.Maui:IEEE Computer Society，2000:3005-3014.
[7]HEINZELMAN W，CHANDRAKASANA，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1(4):660-670.
