無線傳感器網絡中分布式多跳路由算法研究*

尚鳳軍，任東海

(重慶郵電大學計算機科學與技術學院，重慶 400065)

在當今信息技術飛速發展的時代，互聯網為人們提供了快捷的通信平臺，極大地方便了人們的信息交流，無線傳感器網絡技術的產生將徹底改變人類自古以來僅僅靠自身的觸覺、視覺、嗅覺來感知信息的現狀，極大的提高人類獲取信息的準確性和靈敏度［1］。作為信息時代的一項變革性的技術，無線傳感器網絡可以使人們在任何時間、任何地點和任何環境條件下獲取大量詳實、可靠的信息，真正實現“無處不在的計算”理念。無線傳感器網絡是計算機科學技術的一個新的研究領域，具有十分廣闊的應用前景，它的出現引起了全世界范圍的廣泛關注［2］。美國《商業周刊》將無線傳感器網絡列為21世紀高技術領域中的四大支柱型產業之一；《技術評論》雜志也將其列為未來改變世界的10大新興技術之首。可以預言，無線傳感器網絡的發展和廣泛應用，將對人們的社會生活和產業變革帶來極大的影響和產生巨大的推動力。

1 基于退避機制的成簇算法(CHTD)

目前，已經存在多種關于無線傳感器網絡分簇算法的研究。在文獻［3－4］都提到使用時間延遲機制來選擇簇頭，通過給能量較大的節點設置較小的等待時間，從而使剩余能量較多的節點有較大的概率成為簇頭。然而，文獻［3］并未對每輪產生的簇頭數目進行研究，若產生簇頭數目不穩定，簇頭能量消耗過大，進而影響網絡整體的性能。文獻［4］提出的TB-LEACH雖然產生了固定的簇頭數目，但簇頭的位置分布并不均勻，這樣每個簇頭管理的成員節點個數不均勻，導致簇與簇之間能量消耗不均勻，網絡生存時間就得不到有效延長，而且沒有考慮當網絡運行初期節點能量相同的情況下競選簇頭發生的沖突問題。在文獻［5］中，作者研究了單跳和多跳成簇模型的花費以及分組的聚合問題。文獻［6］對LEACH的簇頭選擇方法進行了改進，數據傳輸采用了單跳和多跳相結合的方法，提高了系統的能量效率。文獻［7］引入了定時器方法確定簇頭，保證了能量高的節點優先成為簇頭，提高了網絡的能量效率。文獻［8］提出了一個基于能量和到基站距離的分簇算法，并在簇首的數據發送中引入了改進的多跳路由算法，提高了基站接收到的數據量，延長了整個網絡的壽命。文獻［9］提出了一種非均勻成簇方法，但數據傳輸主要考慮單跳方式。文獻［10］提出了一種分環多跳分簇路由算法，該算法采用分環的方式實現簇頭間的多跳通信，通過在不同環內構建大小不同的簇解決傳感器網絡中存在的“熱點”問題，延長網絡的生命周期。文獻［11］中綜合考慮網絡中節點的剩余能量和節點問傳輸數據的能耗，基于最短路徑樹算法，通過構造兩種不同的權值函數，提出了“比例權值路由算法”，延長了網絡生存時間。但當轉發距離較近時，中間節點的電路消耗造成的總體能量消耗變大和簇頭節點在選擇下一跳路由時，簇頭之間交換信息的開銷問題，同時，基于簇的多跳路由算法中簇頭之間和簇與簇之間的能量平衡問題也需要進一步的改進。另外隨著傳感器網絡應用的拓展，QoS路由算法也成為當前研究的熱點之一［12］。

為了解決以上問題，本文改進了節點的時間延遲機制模型并由此得到延遲時間，使得剩余能量較多的節點有較小的延遲時間，考慮到網絡內節點的能量消耗和負載均衡，引入了最優簇半徑和最佳簇頭數目作用于簇頭的選擇過程當中，在簇數據傳輸過程中引入多跳機制，并著重考慮了中間轉發節點的選擇。實驗證明，本算法使得選出的簇頭更適合擔當數據轉發任務，網絡能量消耗更小，網絡生命周期進一步延長。

1.1 無線傳輸能量模型

由于網絡中路由算法設計首要考慮的因素是能量問題，所以在無線傳感器網絡中，路由算法的設計與信道能量損耗模型息息相關。我們采用與文獻［13］相同的無線通信能量消耗模型。節點發射L比特的數據到距離為d的位置，消耗的能量由發射電路損耗和功率放大損耗兩部分組成，即

其中Eelec表示發射電路損耗的能量。ξfs、ξmp分別為兩種模型中功率放大所需的能量。d0為一個距離常數:

距離大于d0時路徑消耗會相當大，因此一般要求傳輸距離不大于d0，接收k比特的消息，接收機消耗的能量為:

簇頭節點進行本地處理和數據融合的時候，每處理1比特的數據需要的能量損耗EDA。

1.2 CHTD簇頭產生

CHTD算法的執行過程也劃分為“輪”，每一輪分為設置階段和穩定工作階段，在設置階段所有節點組織成簇，穩定工作階段簇頭把監測的數據融合后傳遞到基站。

CHTD算法在每一輪的開始，所有節點并不是立刻就生成隨機數，并根據閥值來申請簇頭，而是要先根據式(4)生成一個定時器，節點i在Ttimer(i)秒后超時。

當某一個節點延遲時間到達時，它將贏得競爭簇頭的權利，擁有競爭權的節點通過自身的簇頭信息集合查看網絡內當前簇頭個數，若已經達到最佳值，節點將不再參與簇頭競爭，并且通過信號接收強度判斷節點和集合中每個簇頭節點之間的距離不小于最優簇半徑，保證每輪的簇頭個數都是最佳值并且均勻分布在監測的區域中。

1.3 CHTD簇頭數量

假設傳感器節點隨機分布在一個區域內，位于r1區域的簇頭的個數為h1，傳感器節點的數量為N1，則每個簇首的能量消耗由接收所有簇成員的信息、融合這些數據、并把融合后的信息傳送給Sink節點3個方面組成［13］。我們假設基站離第1區域比較近，同樣采用自由空間模型進行傳輸，這樣，在一幀中簇首節點消耗的能量為:

l為每個數據的信息位數，EDA為數據融合的消耗。假設網絡中的簇頭節點都按照多跳的方式進行數據的發送，并且每跳的傳輸距離假定為D。

簇內成員節點離簇首的距離假設它不超過自由空間模型的臨界值，這樣，一個非簇首節點的能量消耗為:

如果整個簇內節點的密度是均勻的，那么ρ=N1/()，那么，則

則發送一幀中整個簇的能量消耗為:

那么在R1區域的一幀的總能量消耗為:

忽略電路消耗和數據融合消耗，對Etotal求倒，讓其等于零，得到h1最優簇頭數為:

這個最優值和上面分區域大小的計算是在做了很多假設的情況下得到的，只能作為參考，實際的應用中需要具體考慮和設定。

2 CHTD簇數據傳輸

為了減小遠距離的通信能耗，在CHTD算法的基礎上給出了改進的CHTD多跳路由算法(CHTD-M)，多跳方式是在簇頭間生成一種基于距離能量代價的路由樹，簇頭選擇下一跳節點時，綜合考慮了兩節點間鏈路能耗、接收節點的剩余能量水平和距離基站的位置，通過局部信息動態選擇下一跳，并且通過引入最短有效轉發距離，合理有效的選擇多跳，實驗結果表明改進的CHTD-M進一步優化了網絡中簇頭節點的能量消耗，顯著地延長了網絡的生命周期。CHTD-M的下一跳路由節點在緊鄰的區域內，簇頭節點和它的下一跳路由節點距離不超過自己的通信范圍，很容易實現。

2.1 最優轉發跳數

在無線傳感器網絡中采用多跳的路由機制，雖然能夠降低網絡數據通信的能量開銷，但當節點之間的距離較近時，卻增加了作為路由中間節點的電路能量消耗，有時采用多跳的路由方式所消耗的能量要大于直接傳送的方式，進而在一定的范圍內會增加網絡整體的能量消耗。因此，在簇數據傳輸時應該合理的選擇多跳。假設有N個傳感器節點隨機分布在半徑為r的一個區域內。區域內的傳感器節點按照距離基站的遠近劃分為不同的區域，分別為r1，r2，r3，r4，…，rn，如圖 1。

圖1 無線傳感器網絡多跳模型

在這個區域中有h個簇頭，平均分布于整個區域中，位于rn區域的簇頭節點和基站的通信需要rn－1區域的簇頭節點進行轉發，并且每次通信的距離都不超過自由衰減模型的范圍，為了便于研究，假設每個區域的簇頭節點位于該區域的中部，并且每個區域的環寬度相同都為r，即r1區域的簇頭位于r/2，r2區域的簇頭位于3r/2，r2區域的簇頭節點向基站發送數據時，需要r1區域的簇頭節點轉發數據，r3區域的簇頭向基站發送數據需要r2區域的簇頭節點進行轉發，以此類推，則當位于ri區域的簇頭向基站發送k比特數據時，網絡中的單個簇頭節點發送數據的能耗為:

其中β是數據傳輸經過的跳數，則網絡的總體能量消耗為:

節省能量的跳數可從下面的計算得出:

由(7)可得:

由(8)可知，當網絡中的節點距離基站的距離小于d0時，采用直接傳輸的方式可以節省網絡能量，當網絡中的節點距離基站的距離大于d0時，采用多跳的傳輸方式更能夠節約網絡的能量，我們把這個值定義為節點的最短有效轉發距離(Restriction_distance)。從而可知，一個距離基站距離為d的傳感器簇頭節點i，它的節能轉發跳數βopt=「d/d0?。

在實際應用當中，選擇下一跳路由的轉發節點時，應當綜合考慮整個網絡能量平衡的因素。

2.2 簇間路由樹的生成

在網絡部署完畢后，基站需要用一個給定的發送功率向網絡內廣播一個信號Sink_ADV，節點以此信號強度計算到基站的近似距離。獲得這個距離不但有助于節點在向基站傳輸數據時選擇合適的發送功率來節約能量消耗，而且它還是構造簇間路由樹的必需信息之一。

在有些路由算法中，中繼節點對接收到的數據進行數據融合，然后再斷續發送。實際上，不同簇之間的數據相關性很小［14］，因此在本文中，中繼簇頭節點不再對來自其它簇頭的數據進一步融合，只是簡單的轉發給下一跳。

其中，eij表示節點i和j直接通信的能量消耗，RSSj指節點j接收到Sink_ADV的信號強度，RSSmax是指基站廣播Sink_ADV時的信號強度，D()表示距離估算函數。

綜合考慮能量平衡的因素，本文節點i選擇節點j作為父節點的策略是選擇代價最小的DEC(i，j)，即:

若節點i的鄰居信息表為空，說明此簇頭周圍沒有其它的簇頭存在，這種情況會出現在網絡運行到后期，大部分節點已經死亡的情況下，此時，簇頭將數據直接傳輸給基站。通過式(11)可以看出，DEC(i，j)充分考慮了兩節點間通信的能量消耗和鄰居節點的剩余能量以及到基站的距離狀況，通過對這3個因素的綜合考慮，選擇最小的DEC(i，j)，使得在發送能耗較小的情況下，距離基站較近并且剩余能量充足的節點優先成為父節點。

按照以上策略確定路由方式之后，簇頭生成一棵以基站為根的樹，數據沿著基站的方向傳輸。

2.3 CHTD-M 的分析

通過分析整個算法，CHTD-M算法具有以下兩個特性:(1)算法是完全分布式的，節點完全依賴本地信息決定自身的狀態，無需知道其它節點的位置，具有良好的伸縮性。(2)算法的消息復雜度為O(N)。在整個網絡中，有N個節點參與簇頭競選，最終共選出k個簇頭，每個簇頭廣播一條CH_ADV消息宣布其競選成功，則它們共廣播k條CH_ADV消息，而N－k個簇成員廣播N－k條JOIN_REQ消息。因此，網絡中總的消息開銷為k+N－k=N，所以消息復雜度為O(N)。該特點說明算法的消息開銷較小，能量高效。

我們引入閾值Restriction_distance，若簇頭到基站距離小于Restriction_distance，則直接與基站進等通信。若簇頭到基站距離大于Restriction_distance時，簇頭i的路由選擇方法如下所示。

定義1通信能量消耗 任何兩個可直接通信的節點i、j，通信一次發送k比特數據的能量消耗定義為兩點之間距離dij的函數eij(k，dij)，公式如下:

其中α為功耗指數，與傳輸距離有關。

定義2距離能量代價 若某個簇的當前簇頭為i，j是i的鄰居信息表中的一個簇頭節點，則節點i到節點j的距離能量代價 DEC(Distance Energy Cost)定義如下:

3 仿真分析

本文為了研究在不同的范圍內 LEACH、TBLEACH、CHTD和CHTD-M的性能的差異，分別在兩個場景中進行了模擬，具體見表1，通過仿真網絡的生命周期、接收數據包、能量消耗和負載均衡來觀察改進的CHTD-M的網絡性能。

表1 仿真相關參數

3.1 生命周期

圖2是100 m×100 m場景下的 LEACH、TBLEACH、CHTD和CHTD-M算法中無線傳感器網絡生命周期的對比圖，在場景1中CHTD-M的第一個節點死亡的時間(FND)是LEACH的1.4倍，一半節點死亡(HND)的時間是LEACH的1.2倍。這表明CHTD-M算法使能量的損耗更加均勻的分布到所有節點中，避免了單個節點因能量損耗過大而過早死亡。與TB-LEACH和CHTD相比，CHTD-M算法的FND和HND時間幾乎同時提高了1.1倍左右，這是因為CHTD-M采用了節能跳數，降低了網絡的整體能量消耗。

圖2 100 m×100 m死亡節點和輪的關系

圖3是200 m×200 m場景下的網絡生命周期，在場景2中CHTD-M的優勢進一步得到體現，其FND、HND 時間分別是 LEACH 的3.2 倍、1.3 倍，與TB-LEACH和CHTD相比，CHTD-M的FND時間分別提高了1.9倍和1.3倍，HND時間也幾乎同時提高了1.2倍，這是因為在大場景環境下，其它3種算法的簇頭和基站之間的通信距離加大，簇頭單次的通信能量損耗也隨之加大，而CHTD-M中簇頭和基站之間的通信選擇通信能耗小、離基站較近且能量充裕的簇頭轉發，因此單個簇頭單輪通信能量損耗不會隨區域的增大而大幅增加，并且單輪的簇頭和基站通信的過程中，簇頭之間趨于能量平衡。另外，我們知道從FND到HND的時間跨度能夠反應網絡中節點的能量均衡狀況，跨度越小表明網絡的能量使用越高效。CHTD-M不僅顯著地延長了網絡的生命周期，而且時間跨度也較小，所以在前期，CHTDM算法的網絡中的存活節點和網絡覆蓋面積遠遠大于其它3種算法，在某個時間點，CHTD-M網絡中的節點開始迅速死亡，所以后期的存活節點數量迅速降低，無線傳感器網絡中死亡節點的數目占有一定比例的時候我們就可以認為網絡的死亡，因此，這個不影響CHTD-M在延長無線傳感器網絡生命周期中的優越表現。

圖3 200 m×200 m死亡節點和輪的關系

通過上述分析，我們可知，CHTD-M中的多跳策略可以節省網絡的通信能量消耗，相比LEACH更能夠均衡網絡中不同位置的簇頭節點的能量消耗，減少簇頭節點的通信能量負載，相比TB-LEACH和 CHTD，CHTD-M中的節能跳數策略能夠減少網絡中數據轉發的次數，能夠較小網絡的額外開銷，防止網絡中的電路消耗過大，減弱“熱點問題”對網絡性能的影響。

3.2 能量消耗

圖4是100 m×100 m環境下LEACH、TB-LEACH、CHTD和CHTD-M算法中網絡能量消耗和時間的關系，從圖中可以看出，和CHTD、TB-LEACH和LEACH相比，CHTD-M能夠節省網絡總體能量消耗，經過一段時間后，LEACH的網絡能耗增長速度緩慢，在某一時刻，CHTD-M的網絡總能量消耗大于LEACH，這是因為隨著時間的推移，LEACH中的大部分節點已經死亡，CHTD-M的覆蓋面積遠遠大于LEACH，因此網絡數據的采集量大于它們。

圖4 100 m×100 m環境下LEACH、TB-LEACH、CHTD、CHTD-M能量的消耗

當網絡范圍變大時，CHTD-M的節能效果更加明顯，圖5是在200 m×200 m的環境下，CHTD-M和LEACH、TB-LEACH以及CHTD的能量消耗圖，從圖中可以看出，和TB-LEACH、CHTD相比，CHTD-M在時間為300輪時能夠節約LEACH將近一半的能量，同樣隨著時間的推移，CHTD-M的覆蓋面積遠遠大于LEACH，在某一時刻，CHTD-M的總能量消耗會大于LEACH。

圖5 200 m×200 m環境下LEACH、TB-LEACH、CHTD、CHTD-M能量的消耗

從圖4和5可知，CHTD-M采用多跳的路由策略節省了網絡中通信的能量消耗，和 LEACH、TBLEACH相比，它具有很明顯的節能優勢，而CHTD隨著網絡范圍的逐漸變大達不到CHTD-M的良好性能。

3.3 負載均衡

無線傳感器網絡性能評價的重要標準之一就是網絡負載平衡，為了便于研究，本文將傳感器節點按照它與基站之間的距離等分為兩份，為了便于描述，我們假設第1份覆蓋的范圍為第1區域(距離基站較近的一半節點)，第2份覆蓋的范圍為第2區域(距離基站較遠的一半節點)，統計不同算法中不同區域的節點能量消耗隨時間的變化狀況。

圖6為100 m×100 m環境下CHTD-M各區域能量的消耗和時間的關系，很明顯，在該場景下，CHTD-M中的兩個區域的能量消耗并沒有明顯的差別，其中因為靠近基站的節點需要轉發來自離基站較遠節點的數據，因此能量消耗稍微多于遠離基站的區域，但是這個在可以容忍的范圍之內，通過圖6可以看出，CHTD-M均衡了網絡中不同位置的節點的能量負載，延長了網絡壽命。

圖6 100 m×100 m環境下CHTD-M各區能量的消耗

圖7為200 m×200 m環境下CHTD-M兩個區域的能量消耗，和100×100環境下相比，兩個區域的能量消耗差別稍大，但是，和節點數量增加量相比，兩個區域中單個節點的能量負載基本沒有太大變化，在網絡范圍變大的情況下，CHTD-M依然能夠使網絡中的節點負載趨于平衡，因此，和LEACH以及類似的單跳成簇算法相比，網絡范圍越大CHTDM的優勢越明顯。

圖7 200 m×200 m環境下CHTD-M各區能量的消耗

綜合以上所述，通過對改進算法進行仿真分析，我們得到簇間多跳算法CHTD-M能夠延長網絡的生命周期，增加網絡采集的數據包的數量，節省網絡能量消耗，均衡網絡的能量負載，完善了CHTD成簇算法。

4 總結

本文在對無線傳感器網絡路由算法深入研究的基礎上，總結了目前無線傳感器網絡路由算法研究的主要思路，分析了基于簇的無線傳感器網絡路由算法中存在的問題，設計出了一種完全分布式的、能量有效的無線傳感器網絡分簇算法。主要進行了如下的研究:

(1)基于無線傳感器網絡分簇算法研究分析的基礎上，給出了一種基于時間延遲機制的無線傳感器網絡分簇算法CHTD。該算法建立了節點的時間延遲機制模型并由此得到延遲時間，使得剩余能量較多的節點有較小的延遲時間，從而能夠在每一輪中被優先選為簇頭，達到均衡簇頭能量消耗的目的。此外，該算法還考慮了每輪的簇頭節點個數以及位置分布問題，通過維持每個節點的簇首信息集合使得每輪產生的簇頭數目穩定且位置均勻分布。并通過仿真驗證了CHTD分簇算法比LEACH和目前已有的基于定時器的分簇算法TB-LEACH對網絡性能有明顯改善。

(2)針對CHTD分簇完成之后的簇數據傳輸階段進行算法改進，給出CHTD-M簇間多跳路由算法。該算法將網絡中均勻分布的簇頭構造成一棵路由樹，通過多跳傳輸的方式減少直接與基站通信的簇頭節點數量，從而更進一步的降低能量開銷。同時，該算法還限制了多跳路由的最短轉發距離，降低了中間節點的電路開銷，減少了多跳的數據轉發次數，節省了網絡的能量消耗，弱化了網絡中的“熱點問題”。最后對整體算法進行仿真，實驗結果表明，CHTD-M把節約網絡能量和保持網絡負載平衡結合起來，顯著地延長了網絡的生命周期。

［1］Akkaya K，Younis M.A Survey on Routing Protocols for Wireless Sensor Networks［J］.Ad Hoc Networks，2005，3(3):325－349.

［2］李建中，李金寶，石勝飛.傳感器網絡及其數據管理的概念、問題與進展［J］.軟件學報，2003，14(10):1717－1727.

［3］曹涌濤，何晨，蔣鈴鴿.無線傳感器網絡中基于自適應定時器策略的分簇算法［J］.電子學報，2007，35(9):1719－1723.

［4］Hu Junping，Jin Yuhui，Dou Liang.A Time-Based Cluster-Head Selection Algorithm for LEACH［C］//13th IEEE Symposium on Computers and Communications，2008:1172－1176.

［5］Mhatre V，Rosenberg C.Design Guidelines for Wireless Sensor Networks:Communication，Clustering and Aggregation［J］.Ad Hoc Networks，2004，2(1):45－63.

［6］胡鋼，謝冬梅，吳元忠.無線傳感器網絡路由協議LEACH的研究與改進［J］.傳感技術學報，2007，20(6):1391－1396.

［7］Fan Xiangning，Song Yulin.Improvement on LEACH Protocol of Wireless Sensor Networks［C］//Proceedings of 2007 International Conference on Sensor Technologies and Applications，2007:517－528.

［8］張磊，陳曙.一個新的基于能量和距離的傳感器網絡協議［J］.計算機應用，2008，28(5):1117－1119.

［9］李成法，陳貴海，吳杰，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30(1):27－36.

［10］劉志，裘正定.基于分環多跳的無線傳感器網絡分簇路由算法［J］.通信學報，2008，29(3):104－112.

［11］朱藝華，沈丹丹，吳萬登，等.無線傳感器網絡優化生存時間的動態路由算法［J］.電子學報，2009，37(5):1041－1045.

［12］王寅，尚鳳軍，任東海.一種基于自適應蟻群系統的傳感器網絡 QoS 路由算法［J］.傳感技術學報，2010，23(2):239－244.

［13］Heinzelman W R，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans.on Wireless Communications，2002，1(4):660－670.

［14］Li Chengfa，Ye Mao，Chen Guihai，et al.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks［C］//IEEE International Conference on Mobile Ad-Hoc and Sensor Systems Conference，2005:604－611.