樓宇WSN 能量均衡路由算法

尚志文，李曉卉，趙 兵，梁曉兵

（1.武漢科技大學 信息科學與工程學院，湖北 武漢430081；2.中國電力科學研究院，北京100192）

0 引 言

如何設計更加優化的樓宇無線傳感器網絡 （wireless sensor networks，WSN）［1，2］路 由、平 衡 網 絡 能 量 消 耗 是 降低樓宇WSN 節點的能耗、延長網絡生存期的重要問題。

WSN 路由主要分為兩個大類，分簇路由［3］和平面路由［4，5］。分簇路由是以LEACH 算法為代表的一系列WSN分簇路由，該算法簇頭選擇隨機性太大，若簇頭相距過近或者簇頭處于網絡邊緣，則部分遠離簇頭的節點容易能耗過大而提前死亡［6］，并且該算法通常應用在大規模WSN中，而樓宇WSN 屬于小型WSN。以AODVjr協議［7］和DD協議［8］等為代表的平面路由協議主要都是通過發現一條距離最短、能耗最小的路徑來路由數據包，但是單條路徑能耗最小并不代表能延長整個WSN 的生命期，倘若頻繁地使用同一條路徑，會使該條路徑上的節點過早耗盡電能，從而縮短了整個網絡的生命期。

為解決以上問題，本文提出一種適用于樓宇WSN 的能量均衡路由算法 （energy－balancing routing for WSN using in building，EBR－WSNB）。該算法在平面路由協議的基礎上，引入路由負載的概念，通過路由負載值修改路由表，使網絡達到負載均衡，延長整個網絡生命期。

1 網絡模型

本文旨在研究樓宇WSN［9］，其特點是該網絡模型是由一個匯聚節點和m 行n 列的N（N＝m×n，其中m、n 均為大于2的正整數）個節點組成的網絡。假設有一棟3層高的樓宇即m＝3，每層樓4個房間即4個無線傳感器節點，n＝4。采用ZigBee布網［10］，協調器 （coordinator）位于中間樓層的最頂端，用于運行路由算法、控制整個網絡以及采集網絡數據。因此該網絡模型可等效為3行4列一共12個節點和一個匯聚節點的網絡，如圖1所示。

圖1 3行4列的樓宇WSN 拓撲結構

從圖1所示的網絡模型可以看出，該網絡是一個布局規則的網絡。在實際生活中，樓宇WSN 中各個節點位置相對固定，因此它們都可以等效成與圖1類似的規則網絡。

2 樓宇WSN 能量均衡路由算法 （EBR－WSNB）

2.1 路由負載 （RL）

有關研究結果表明，WSN 中處理器和各種傳感器模塊的功耗隨著技術的進步越來越低，無線通信模塊是WSN 中最消耗能量的部分［11］。而節點的能耗則與路由的數據包數量有關，一個節點路由的數據越多，消耗的能量就越多，這必然導致網絡中各個節點能耗不均衡。

為了更清楚的觀察節點能耗，本文定義路由負載RL（routing load）來衡量通過某個節點i的數據包量占路由數據包總量的比例。樓宇WSN 中內層節點既要發出本節點的數據包，又要接收并轉發上一跳節點上傳的數據包，而終端節點只發出本節點數據包，因此節點i的路由負載RLi的數學模型應該由兩部分組成

式中：Di——節點i每秒路由的數據包數目；li——節點i所在網絡層數depth；iLH——節點i的上一跳節點的集合；x——節點i的上一跳節點的集合中的一個節點；xNH——節點x 的下一跳節點；RLx——節點x 的路由負載；NxNH——節點x 的下一跳節點個數，N——子節點的總個數。

需要注意的是，由式 （1）可以看出，計算某個節點i的RLi需要先計算出該節點的上一跳節點的RLx值，所以計算時應從終端節點逐層往上層計算。

假設在如圖1 所示的網路中運行ZigBee 網絡中的AODVjr路由算法找到了一條最短路徑，設定每個節點每秒發出一個數據包。下面計算depth＝3 層的各個節點的RL值

從上面的計算結果可以看出，除了根節點所在層以外，同層節點的路由負載不均衡，同理可以算出其它層節點路由負載也是如此，因為中間部分節點的上一跳節點數較多，負載的數據包也就相對較多，自然就會消耗更多能量，造成網絡能量消耗不均衡的現象。

2.2 EBR－WSNB算法步驟

為了平衡樓宇WSN 中各個節點的能耗，需要有效均衡WSN 中節點的RL。因此本文提出一種通過減少網絡邏輯鏈路達到修正RL的方法來建立路由表。

EBR－WSNB算法實現過程如下：

（1）算法初始化

初始化網絡，匯聚節點在收集到網絡拓撲信息后，將網絡配置成m 行n 列的基本的網絡拓撲，并在每個節點的路由表中添加 “路由次數”條目。

（2）建立優化的網絡拓撲

在初始網絡拓撲的基礎上，根據式 （1）計算每層各個節點的RL，并計算該層各個節點RL 值的方差基本值。利用RL值的方差來判斷當前層的負載是否均衡，方差越小則表示本層各個節點的RL 值越相近，本層節點的負載也就越均衡。RL的方差越大說明當前層負載不均衡。此時若每層只存在一個RL最大的節點，需要將該RL最大的節點與其上一跳節點間的邏輯鏈接依次刪除，刪除后重新計算本層各節點的RL 和方差，如果方差達到最小，則保存此時的路由表，如果方差沒有達到最小，則恢復之前路由表，重復進行刪除操作，直到刪除某條邏輯鏈路之后，當前層節點的RL 值的方差達到最小時，保存此時的路由表；若每層存在兩個以上RL 最大的節點，則對除去最高一行和最低一行以外的所有中間行節點同時進行上述刪除操作，直到當前層節點的RL 值的方差達到最小時，保存此時的路由表。

（3）數據傳遞

無論是發送數據包還是接收數據包，都要在發送和接收到數據包的節點的路由表的 “路由次數”條目上加1，節點向下一跳節點發送數據包時，優先選擇 “路由次數”最小的節點進行傳遞，若存在兩個以上 “路由次數”最小的節點，則依次選擇進行傳遞。

EBR－WSNB算法如圖2所示。

圖2 EBR－WSNB算法

該算法的核心是刪除了負載最大的節點的邏輯鏈接之后，同層節點的RL 值會相對均衡，按新的網絡邏輯鏈接更新路由表。由于設備可能隨機的選擇可以連接的下一跳節點，節點每發送或者接收一次數據包，就在 “路由次數”條目上加1計數，當某個節點要選擇下一跳節點時，優先選擇 “路由次數”小的節點連接，即剩余能量較多的節點進行傳輸，即可進一步達到能耗均衡。

將以上算法應用到圖1所示網絡中，對于depth＝1層的節點，節點2的RL 值最大，依次刪除節點2與節點4、節點5和節點6的邏輯鏈接，并重新計算各個節點的RL和該層各節點RL 的方差，最后由計算結果可以看出，在刪除節點2和節點5的邏輯鏈接后，depth＝1層的節點的RL的方差達到最小，因此保存移除節點2和節點5的邏輯鏈接之后的路由表，以此類推，對depth＝2和depth＝3層的節點也進行以上操作，直到depth＝2和depth＝3層中的節點的RL都達到相對均衡即方差最小后，保存路由表，即可得到如圖3所示的網絡拓撲結構。

圖3 運行EBR－WSNB算法之后的網絡拓撲

計算圖3所示網絡拓撲結構中各個節點的RL值，并且將其與AODVjr算法即圖1所示網絡拓撲結構相比，結果見表1。

表1 AODVjr算法與EBR－WSNB算法RL值對比

通過表1可以看出在AODVjr算法中，depth＝4層的節點RL 值相同，因為它們沒有上一跳節點。越往高層，RL值相對越大，即消耗的能量就越多，因為內層累積數據量越來越大。節點2、節點5和節點8的RL 值分別大于與它們同層的其它兩個節點，因為它們可連接的上一跳節點數較多，正因為如此，節點2、節點5和節點8耗能就會比跟它們同層的其它兩個節點更快，所以就造成了網絡能量消耗不均勻的現象，最終就會導致整個網絡過早癱瘓。這就是傳統AODVjr算法應用在此網絡中的缺陷。

由表1可以看出EBR－WSNB算法明顯均衡了網絡各層中節點的RL，使各層中的各個節點可以均衡消耗能量，但是它在降低中間節點RL 值的同時，增大了該層其它節點的RL值，這是由于其它節點分擔負載導致的，而每層以及整個網絡的路由負載總量并沒有改變，由此說明，整個網絡耗能總量是沒有變的，該算法只是均衡了負載，從而達到延長網絡生命期的目的。

3 算法仿真

3.1 仿真場景及參數

本文仿真的實驗場景是一座3層高的教學樓，每層樓4個教室，每個教室一個ZigBee傳感器節點，而coordinator安裝在中間樓層即第二層的最頂端。初始網絡拓撲如圖1所示。傳感器運行過程中，每秒發送一個數據包。每個節點的初始能量為2J，每發送一個數據包耗能1mJ，每接收一個數據包耗能0.5mJ，直到任何一個節點耗盡能量為止結束仿真。實驗通過對比本文算法和AODVjr算法性能，驗證本文算法的優越性。

3.2 仿真結果分析

3.2.1 網絡生命期比較

分別在仿真場景中運行AODVjr算法和EBR－WSNB算法，直到出現第一個耗盡能量的節點為止，記為整個網絡的生命期，仿真結果見表2。

表2 網絡生命期對比

通過表1和表2可以看出，雖然整個網絡耗能總量沒有變，但是通過EBR－WSNB算法使各個節點分擔路由量，能量得以均衡消耗，從而整個網絡生命期有了大幅度的提升。

3.2.2 各節點耗能比較

由表2知，在AODVjr算法下，該仿真網絡生命期只有157s，下面對比兩種算法在第157s時各個節點的能耗總量。如圖4所示。

由圖4 可以看出，AODVjr算法下，各層中各個節點的能耗非常不均衡，正因為如此，才會出現某個節點提前耗盡能量而 “死亡”的現象，從而導致整個網絡癱瘓。正如圖4中的節點1，在第157s已經耗盡能量，而與它同層的節點3耗能卻還很少，節點1 “死亡”之后，盡管它的上一跳節點還可以選擇其它的路徑傳遞數據，但是之后整個網絡的數據全都負擔到了節點2和節點3上，加速了它們的能量消耗，整個網絡也會很快陷入癱瘓。然而在EBRWSNB算法下，各層中各個節點能耗均衡，不會出現某一個節點提前耗盡能量的現象，從而整個網絡生命期得以延長。

圖4 在第157s時兩種算法下各節點耗能量比較

3.2.3 網絡節點數變化影響比較

本文前面的討論和仿真都建立在3 行4 列的網絡中，實際應用中網絡規模可能更大。在上面仿真場景其它條件不變的情況下，增加網絡節點個數，然后在比較兩種算法下網絡生命期，結果如圖5所示。

圖5 節點數變化對網絡生命期的影響

從圖5可以看出，隨著網絡節點數的增加，網絡生命期逐漸減小，因為節點數越多，網絡數據量越大，越靠近匯聚節點的節點路由負載越大，自然耗能就越快。但是無論節點數怎么變化，整個網絡在本文所述的EBR－WSNB算法下比傳統的AODVjr算法網絡生命期長，體現了本文所述算法的優越性。

需要說明的是，當樓層過高時，若把匯聚節點安放在中間樓層，上、下部分樓層將連接不到匯聚節點，這時需要在depth＝1 層節點與匯聚節點之間再安置足夠數量的router保證數據能順利傳送到匯聚節點。

4 結束語

本文提出一種基于路由負載RL 的路由建立算法，該算法通過更新RL 值動態修改路由表達到能量均衡的路由選擇。算法仿真結果表明，相比于傳統的AODVjr路由算法，該算法在樓宇WSN 中能更好的均衡網絡能量消耗，延長網絡生命期。

不可忽略的是，該算法是以較大的路由表的存儲空間換取網絡生命期的延長，在算法運行過程中要執行一定的運算，因此未來將進一步簡化運算過程并在實際的樓宇網絡中驗證算法的有效性。

［1］ZHAO Wenjing，QIN Huibin，WU Jianfeng，et al.The design of intelligent building environment monitoring system based on ZigBee technology ［J］.Mechanical and Electrical Engineering，2010 （8）：114－117 （in Chinese）.［趙文靜，秦會斌，吳建鋒，等.基于ZigBee技術的智能樓宇環境監測系統的設計［J］.機電工程，2010 （8）：114－117.］

［2］LEI Juan，CHEN Yang.The applications of sensors in intelligent building ［J］.Silicon Valley，2012 （2）：116 （in Chinese）. ［雷娟，陳陽.傳感器在智能樓宇中的應用 ［J］.硅谷，2012 （2）：116.］

［3］Liu X.A survey on clustering routing protocols in wireless sensor networks［J］.Sensors，2012，12 （8）：11113－11153.

［4］Saravanan T，Saritha G，Srinivasan V.An analysis of flat routing protocols in sensor N／W ［J］.Middle－East Journal of Scientific Research，2014，20 （12）：2566－2570.

［5］LI Yuntao，ZHU Min，LIU Haolin，et al.Wireless sensor network routing algorithm based on energy equilibrium ［J］.Journal of Sichuan University （Natural Science Edition），2012（1）：69－74 （in Chinese）.［李運濤，朱敏，劉昊霖，等.基于能量均衡的無線傳感網絡路由算法 ［J］.四川大學學報 （自然科學版），2012 （1）：69－74.］

［6］CHEN Xiaojuan，WANG Zhuo，WU Jie.An improved WSN routing algorithm based on LEACH ［J］.Journal of Sensing Technology，2013 （1）：116－121 （in Chinese）. ［陳曉娟，王卓，吳潔.一種基于LEACH 的改進WSN 路由算法 ［J］.傳感技術學報，2013 （1）：116－121.］

［7］Niu Yingqi，Bie Hongxia.An improved AODVjr algorithm for extending network lifetime［C］／／3rd IEEE International Conference on Network Infrastructure and Digital Content，2012：18－21.

［8］Tang Junhua，Dai Sisi，Li Jianhua，et al.Gossip－based scalable directed diffusion for wireless sensor networks ［J］.International Journal of Communication Systems，2011，24 （11）：1418－1430.

［9］Ahamed SI，Wang W，Hong J.Recent advances in energy－efficient sensor networks ［J］.International Journal of Distributed Sensor Networks，2013.

［10］Guo X，Liu H，Zhou P，et al.Design of building energy consumption monitoring system based on ZigBee technology［J］.Computer Measurement ＆ Control，2011，19 （3）：551－553.

［11］MENG Xiaoyan.Simulation of wireless sensor network communication node optimization selection algorithm ［J］.Computer Simulation，2013，30 （2）：205－208 （in Chinese）.［孟小艷.無線傳感網絡通信節點優化選擇算法仿真 ［J］.計算機仿真，2013，30 （2）：205－208.］