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

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

0 引 言

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

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

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

1 網(wǎng)絡模型

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

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

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

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

2.1 路由負載 （RL）

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

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

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

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

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

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

2.2 EBR－WSNB算法步驟

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

EBR－WSNB算法實現(xiàn)過程如下：

（1）算法初始化

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

（2）建立優(yōu)化的網(wǎng)絡拓撲

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

（3）數(shù)據(jù)傳遞

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

EBR－WSNB算法如圖2所示。

圖2 EBR－WSNB算法

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

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

圖3 運行EBR－WSNB算法之后的網(wǎng)絡拓撲

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

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

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

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

3 算法仿真

3.1 仿真場景及參數(shù)

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

3.2 仿真結果分析

3.2.1 網(wǎng)絡生命期比較

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

表2 網(wǎng)絡生命期對比

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

3.2.2 各節(jié)點耗能比較

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

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

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

3.2.3 網(wǎng)絡節(jié)點數(shù)變化影響比較

本文前面的討論和仿真都建立在3 行4 列的網(wǎng)絡中，實際應用中網(wǎng)絡規(guī)?？赡芨?。在上面仿真場景其它條件不變的情況下，增加網(wǎng)絡節(jié)點個數(shù)，然后在比較兩種算法下網(wǎng)絡生命期，結果如圖5所示。

圖5 節(jié)點數(shù)變化對網(wǎng)絡生命期的影響

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

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

4 結束語

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

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

［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技術的智能樓宇環(huán)境監(jiān)測系統(tǒng)的設計［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）.［李運濤，朱敏，劉昊霖，等.基于能量均衡的無線傳感網(wǎng)絡路由算法 ［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）.［孟小艷.無線傳感網(wǎng)絡通信節(jié)點優(yōu)化選擇算法仿真 ［J］.計算機仿真，2013，30 （2）：205－208.］