張 健

(安徽三聯(lián)學(xué)院 計算機工程學(xué)院，安徽 合肥 230001)

基于多目標優(yōu)化函數(shù)的無線傳感器網(wǎng)絡(luò)負載均衡路由協(xié)議

張 健

(安徽三聯(lián)學(xué)院 計算機工程學(xué)院，安徽 合肥 230001)

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

無線傳感器網(wǎng)絡(luò)；多目標優(yōu)化函數(shù)；能量效率；路由跳數(shù)；網(wǎng)絡(luò)生存期

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

1 無線傳感器網(wǎng)絡(luò)覆蓋感知模型

本研究構(gòu)建的無線傳感器網(wǎng)絡(luò)覆蓋感知模型包括無線傳感器網(wǎng)絡(luò)覆蓋技術(shù)和網(wǎng)絡(luò)模型，其中無線傳感器網(wǎng)絡(luò)所研究的覆蓋技術(shù)的目的：

(1)使待監(jiān)測區(qū)域中的每一個節(jié)點都至少在一個傳感器節(jié)點的覆蓋范圍內(nèi)。

(2)在保證覆蓋要求的基礎(chǔ)上，同時減少網(wǎng)絡(luò)節(jié)點消耗、延長網(wǎng)絡(luò)壽命。

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

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

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

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

2 多目標優(yōu)化函數(shù)路由協(xié)議設(shè)計

針對傳統(tǒng)協(xié)議的不足，設(shè)計了多目標優(yōu)化函數(shù)路由協(xié)議。下面將詳細介紹源節(jié)點選取和最優(yōu)路徑建立的過程。

2.1 源節(jié)點的選取機制

當某個觸發(fā)事件發(fā)生時，覆蓋區(qū)域內(nèi)被喚醒的節(jié)點集合S形成后，源節(jié)點的選取步驟如下：

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

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

2.2 最優(yōu)路徑的建立過程

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

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

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

TTL為報文的生存時間，即路徑的最大跳數(shù)長度，報文每經(jīng)過一次轉(zhuǎn)發(fā)，TTL值減1[4,7]。

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

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

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

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

因此，通過最優(yōu)上一跳矢量的確定和擴展探測報文的逐跳傳輸完成，網(wǎng)絡(luò)中的最優(yōu)路徑初步建立起來。

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

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

(4)功率控制技術(shù)。最優(yōu)路徑最終確立后，節(jié)點之間進行數(shù)據(jù)轉(zhuǎn)發(fā)。本協(xié)議較之傳統(tǒng)路由協(xié)議，優(yōu)點主要體現(xiàn)在節(jié)點的發(fā)送功率不是恒定不變，而是隨著信道狀態(tài)的改變而改變，以提高數(shù)據(jù)傳輸?shù)哪芰啃?。信道狀態(tài)與發(fā)送功率大小成反比關(guān)系，即當信道狀態(tài)較好時，節(jié)點降低發(fā)送功率以減少能耗；反之，節(jié)點提高發(fā)送功率以確保數(shù)據(jù)傳輸可靠性。其實，在增強包中所包含的節(jié)點所期望的信噪比等信息是實現(xiàn)功率控制的重要參數(shù)?？紤]無線信道的特性，節(jié)點在周期性地收到增強包后會更新自己的發(fā)送功率大小[16]。

3 協(xié)議仿真

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

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

(1)數(shù)據(jù)包發(fā)送成功率分析

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

(2)網(wǎng)絡(luò)可用能量分析

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

(3)網(wǎng)絡(luò)死亡節(jié)點比率分析

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

4 總結(jié)

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

[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] 馮維. 基于離子群算法求解多目標函數(shù)優(yōu)化[D]. 長春: 吉林大學(xué), 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] 周曉芳. 無線傳感器網(wǎng)絡(luò)中路由協(xié)議的跨層設(shè)計研究[D]. 合肥: 中國科學(xué)技術(shù)大學(xué), 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] 陳樂瑞, 孔金生. 基于改進遺傳算法的網(wǎng)絡(luò)路由優(yōu)化研究[J]. 計算機應(yīng)用與軟件, 2013, 30(4): 135-137.

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

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

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

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

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

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

[13] 楊云, 李斌, 高峰, 等．無線傳感器網(wǎng)絡(luò)簇內(nèi)優(yōu)化的最小跳數(shù)路由算法[J]．計算機應(yīng)用與軟件, 2010, 27(2): 31-46．

[14] 劉少卿. 無線傳感器網(wǎng)絡(luò)負載均衡路由協(xié)議研究[D]. 鎮(zhèn)江: 江蘇大學(xué), 2010.

[15] 任建華，李元誠，楊洪. 基于路徑寬度的Zigbee網(wǎng)絡(luò)路由算法優(yōu)化[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

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

張健，男，安徽泗縣人，碩士，安徽三聯(lián)學(xué)院計算機工程學(xué)院講師，研究方向為無線傳感器網(wǎng)絡(luò)。

時間：2016-1-5 13:01 網(wǎng)絡(luò)出版地址：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