基于多目標優化函數的無線傳感器網絡負載均衡路由協議

張 健

(安徽三聯學院 計算機工程學院，安徽 合肥 230001)

基于多目標優化函數的無線傳感器網絡負載均衡路由協議

張 健

(安徽三聯學院 計算機工程學院，安徽 合肥 230001)

針對目前無線傳感器網絡路由協議在延長網絡生存期和提高網絡整體性能等方面存在的缺陷，以平衡網絡中節點能量消耗、延長網絡生存期為優化目標，提出了一種基于多目標優化函數路由協議。該協議將節點可用能量、路由跳數和節點之間物理距離等參數引入到路由選擇函數中，以實現最優路徑的建立和對無線傳感器網絡性能的綜合優化。NS2仿真結果表明，與傳統的定向擴散協議相比，數據發送成功率提高了15.3%，網絡能量利用率提升了9.7%，網絡生存期延長約12%，在無線傳感器網絡中具有顯著的優越性。

無線傳感器網絡；多目標優化函數；能量效率；路由跳數；網絡生存期

無線傳感器網絡[1]是由大量傳感器節點組成的無線自組織網絡，是當前國內外備受關注的新興研究領域。由于無線傳感器網絡節點的自身特性使得對協議的制定提出了很大的挑戰，提高節點能量效率是研究人員設計協議的首要目的[2]。本文提出一種以平衡網絡中節點能量消耗、延長網絡生存期等為優化目標的多優化函數路由協議。該協議將節點之間物理距離、節點到源節點的路由跳數和節點當前可用能量等變量引入到路由選擇函數中，以實現最優路徑的建立，并針對無線信道的特點在數據傳輸過程中應用了功率控制技術，從而提高了整個網絡性能的穩定性，實現了對無線傳感器網絡性能的綜合優化[3]。

1 無線傳感器網絡覆蓋感知模型

本研究構建的無線傳感器網絡覆蓋感知模型包括無線傳感器網絡覆蓋技術和網絡模型，其中無線傳感器網絡所研究的覆蓋技術的目的：

(1)使待監測區域中的每一個節點都至少在一個傳感器節點的覆蓋范圍內。

(2)在保證覆蓋要求的基礎上，同時減少網絡節點消耗、延長網絡壽命。

網絡模型假定：V是所有傳感器節點的集合，L是網絡中邏輯鏈路的集合構成一個無向連通圖G=(V，L)； 觸發事件發生時，覆蓋區域內被喚醒的節點集合S，顯然有S?V； 為將無向連通圖G變成雙向連通，需對節點之間形成的邊進行增刪。

文中采用的符號說明如下。

H(i)：覆蓋區域內節點i到達源節點s的跳數；N-(i)：覆蓋區域內節點i的上一跳鄰居集合，即任給j∈N-(i)，有H(j)=H(i)-1；N+(i)：覆蓋區域內節點的下一跳鄰居集合，即任給j∈N+(i)，有H(j)=H(i)+1；D(i,j)：覆蓋區域內節點i和節點j之間的物理距離；E(j)：覆蓋區域內節點j的當前可用能量；Q(i,j)：覆蓋區域內節點i和節點j之間鏈路的質量函數，該值越大，鏈路質量越好；L(i)：覆蓋區域內節點i最優上一跳矢量，方向指向上一跳節點N-(i)，大小為兩者之間的物理距離。

假設給定G=(V,L)，S和基站B，問題抽象為如何在觸發事件源位置和基站B之間尋找最優路徑及數據采用何傳輸方式，以確保數據傳輸可靠性、提高能量效率，進而延長網絡生存期[4]。

2 多目標優化函數路由協議設計

針對傳統協議的不足，設計了多目標優化函數路由協議。下面將詳細介紹源節點選取和最優路徑建立的過程。

2.1 源節點的選取機制

當某個觸發事件發生時，覆蓋區域內被喚醒的節點集合S形成后，源節點的選取步驟如下：

(1)事件源發生后，S中的節點會廣播標示本節點ID和信號強度值的簡短報文。信號強度的大小可由節點的傳感器模塊獲知。

(2)S中的每個節點將接收到的簡短報文中的信號強度值和自己信號強度值進行比較。如果節點接收到的信號強度值小于自己的信號強度值，則該節點繼續廣播標示自己的ID和信號強度值的簡短報文，反之，該節點停止廣播自己的簡短報文。經過一段時間后，感知到最強信號的節點不再收到標示更強信號強度的報文，這時該節點被選作源節點s[4-5]。

2.2 最優路徑的建立過程

本協議中，最優路徑是源節點s在網絡中通過擴散探測報文逐跳建立起來；然后基站B通過增強包向源節點s反向確認后，最優路徑才最終建立起來[4,6]。

(1)廣播探測報文。源節點s在網絡中通過廣播方式擴散初始探測報文， 其IP報文頭部格式如表1所示。

表1 初始探測報文IP報文頭部格式

TTL為報文的生存時間，即路徑的最大跳數長度，報文每經過一次轉發，TTL值減1[4,7]。

從源節點s接收到初始探測報文后，任一中轉節點i(非基站)將自己的ID、到源節點的跳數、可用能量等信息添加在初始探測報文的附加IP頭部內，生成擴展探測報文，其IP報文頭部格式如表2所示。

表2 擴展探測報文的IP報文頭部格式

在完成估測D(i,s)后，中轉節點i將生成的擴展探測報文轉發給下一跳鄰居節點，下一跳鄰居節點在接收到擴展探測報文后也要生成自己的擴展探測報文和估測到源節點s物理距離，然后再向下一跳節點轉發其擴展探測報文，以此類推，直到報文轉發到基站B或者轉發失敗[9]。

(2)建立最優路徑。下一跳節點在收到上一跳節點轉發過來的擴展探測報文后，就獲得了上一跳節點的信息和物理距離大小。因此最優上一跳矢量L(i)可以通過下一跳節點來綜合比較其上一跳鄰居節點的信息和物理距離大小來獲得[10-11]，也可以通過鏈路的質量函數Q(i,j)最大值來確定路徑中的每個節點的最優上一跳矢量。

因此，通過最優上一跳矢量的確定和擴展探測報文的逐跳傳輸完成，網絡中的最優路徑初步建立起來。

(3)增強最優路徑。當從源節點s基站B的最優路徑建立后，基站B沿著最優路徑反向向上一跳鄰居節點以較小的時間間隔周期性地轉發增強包。同樣，最優路徑上的任一節點i將其增強包轉發給最優上一跳節點，任一節點i的增強包IP報文頭部格式如表3，增強包中SNRi表示節點i希望最優上一跳節點發送給自己的信噪比的值，信噪比越大，表明信道狀態越好。當源節點s接收到最優下一跳節點轉發來的增強包后，最優路徑最終確立[14-15]。

表3 增強包IP報文頭部格式

(4)功率控制技術。最優路徑最終確立后，節點之間進行數據轉發。本協議較之傳統路由協議，優點主要體現在節點的發送功率不是恒定不變，而是隨著信道狀態的改變而改變，以提高數據傳輸的能量效率。信道狀態與發送功率大小成反比關系，即當信道狀態較好時，節點降低發送功率以減少能耗；反之，節點提高發送功率以確保數據傳輸可靠性。其實，在增強包中所包含的節點所期望的信噪比等信息是實現功率控制的重要參數。考慮無線信道的特性，節點在周期性地收到增強包后會更新自己的發送功率大小[16]。

3 協議仿真

使用NS2(NetworkSimulatorversion2，ns-allinone-2.34)仿真該協議和定向擴散路由協議[10]，并從數據發送成功率、節點當前可用能量、節點死亡比率3方面進行比較和性能分析。

仿真場景設計采取在300m×300m的網絡覆蓋面積，設置了30個傳輸半徑為100m的傳感器節點。當路由事件發生時，首先采取源節點選取機制選定源節點，該源節點周期性地(源節點等待時間為60s)廣播探測報文(70B)，仿真時間進行500s。

(1)數據包發送成功率分析

從圖1中可以看出，多目標優化函數路由協議的數據包發送成功率一直高于定向擴散路由協議。通過計算可以得到多優化函數的端到端數據包發送成功率可以比定向擴散協議高出15.3%。一方面，由于鏈路的質量函數Q的應用，使得節點之間的物理距離D(i,j)減小，有利于提高節點之間的數據發送成功率；另一方面，功率控制技術的應用，對信道狀態較差時，調整數據發送功率，有利于提高節點間的數據發送成功率。

(2)網絡可用能量分析

圖2仿真結果顯示隨著網絡運行時間的推移，網絡的可用能量隨之減少。在多目標優化函數協議和定向擴散協議中，同一個觸發事件均可以喚醒多個節點，在被喚醒節點數量較少時，多目標優化函數的源選取機制并不明顯。隨著時間推移，當被喚醒節點數量達到一定數值時，多目標優化函數協議發送的探測報文比定向擴散協議發送的少很多，有效地實現了節能，網絡能量利用率提升9.7%。

(3)網絡死亡節點比率分析

圖3仿真結果顯示，隨著時間的推移，多目標優化函數路由協議的節點死亡比率明顯小于定向擴散協議，特別是在采用功率控制技術，使得網絡生存期延長約12%。因為功率控制技術有效的減少了數據傳輸過程中的能量消耗，從而延長網絡生存期。

4 總結

本文提出了一種多目標優化函數的無線傳感網絡負載均衡路由協議。該協議將節點可用能量、路由跳數和節點之間物理距離等參數引入到路由選擇函數中，以實現最優路徑的建立，實現了對無線傳感器網絡性能的綜合優化，并采用了功率控制技術，有效地提高了數據傳輸過程中的能量效率，達到網絡整體性能優化。通過仿真實驗，證明了本文提出的優化算法與傳統定向擴散算法相比，在平衡網絡能量消耗和延長網絡生存期方面更優。下一步工作可以圍繞路由協議的服務質量支持和降低算法的復雜度來開展，在降低能量消耗和服務質量間達到平衡，實現全局最優路由策略。

[1]S. H. Kim. Location-free semi-directional flooding for on-demand routing in low-rate wireless mesh networks[C]. Proc. of the 20th International Conference on Computer Communications and Networks: IEEE Press, 2011.

[2] 馮維. 基于離子群算法求解多目標函數優化[D]. 長春: 吉林大學, 2010.

[3] T. F. Shih, H. C. Yen. Location-aware routing protocol with dynamic adaptation of request zone for mobile ad hoc networks[J]. Wireless Networks, 2008, 14(1): 321-333.

[4] 周曉芳. 無線傳感器網絡中路由協議的跨層設計研究[D]. 合肥: 中國科學技術大學, 2010.

[5] K. K. Lee, S. H. Kim, H. S. Park. An effective broadcast strategy for route discovery in the zigBee network[C]. Proc. of the 10th International Conference on Advanced Communication Technology: IEEE Press, 2008.

[6] 陳樂瑞, 孔金生. 基于改進遺傳算法的網絡路由優化研究[J]. 計算機應用與軟件, 2013, 30(4): 135-137.

[7] 周曉芳, 屈玉貴. 一種基于多優化函數的跨層定向擴散路由協議[J]. 中國科學技術大學學報, 2009, 39(8): 798-803.

[8] 陶志勇, 路筍．基于ZigBee的修正加權質心定位算法研究與實現[J]. 計算機應用與軟件, 2014, 31(1): 123-126．

[9] 張培軍, 李曉霞, 姬志強. 基于MATLAB遺傳工具箱的多目標函數優化[J]. 航海工程, 2009, 38(1): 49-51.

[10] 許建真, 姚麗潔, 袁桂敏．一種基于LEACH協議的簇頭選擇改進算法[J]．計算機應用與軟件, 2012, 29(11): 262-263, 268．

[11] 王淑華，陳國定，趙國炳．一種無線傳感器網絡能耗模型及有效性分析[J]．計算機應用與軟件，2011，28(2)：215-217．

[12] 張俊虎, 彭輝, 邵峰晶．移動傳感器網絡路由協議的多跳數據傳輸及能耗性能分析[J]. 計算機應用與軟件, 2011, 28(11): 202-206．

[13] 楊云, 李斌, 高峰, 等．無線傳感器網絡簇內優化的最小跳數路由算法[J]．計算機應用與軟件, 2010, 27(2): 31-46．

[14] 劉少卿. 無線傳感器網絡負載均衡路由協議研究[D]. 鎮江: 江蘇大學, 2010.

[15] 任建華，李元誠，楊洪. 基于路徑寬度的Zigbee網絡路由算法優化[J]. 計算機工程，2014, 40(1): 117-120.

Load Balancing Routing Protocol for Wireless Sensor Networks Based on Multi-object Optimization Function

ZHANG Jian

(School of Computer Engineering, Anhui Sanlian University, Hefei 230001, China)

To avoid the deficiencies of present wireless sensor network routing Protocol in extending network lifetime and improving network performance, a routing algorithm based on multi-object optimization functions is proposed to achieve the optimization goals of balancing network node energy consumption and extending network lifetime. Optimum path is set up by introducing parameters like available energy of nodes, routing hops and physical distance between nodes into routing selection function. In this way, the integrated optimization of wireless sensor network performance is achieved. We conduct a NS2 emulation experiment and the result shows, our proposed algorithm have achieved higher transmission reliability, lower energy consumption and much longer network lifetime. Compared with traditional directed diffusion algorithms, the rate of data transmission success raises by 15.3%, utilization ratio of network energy by 9.7%, and network lifetime by 12%. Generally our proposed method has more advantages in wireless sensor networks.

wireless sensor networks, multi-object optimization functions, energy efficiency, routing hops, network lifetime

2015-03-05

安徽省教育廳高等學校省級自然科研項目(KJ2013B090)。

張健，男，安徽泗縣人，碩士，安徽三聯學院計算機工程學院講師，研究方向為無線傳感器網絡。

時間：2016-1-5 13:01 網絡出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160105.1301.009.html

TP301.6

A

1007-4260(2015)04-0033-04

10.13757/j.cnki.cn34-1150/n.2015.04.009