張 健

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

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

張 健

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

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

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

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

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

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

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

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

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

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

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

2.1 源節(jié)點(diǎn)的選取機(jī)制

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

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

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

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

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

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

表1 初始探測報(bào)文IP報(bào)文頭部格式

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

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

表2 擴(kuò)展探測報(bào)文的IP報(bào)文頭部格式

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

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

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

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

表3 增強(qiáng)包IP報(bào)文頭部格式

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

3 協(xié)議仿真

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

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

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

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

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

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

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

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

4 總結(jié)

本文提出了一種多目標(biāo)優(yōu)化函數(shù)的無線傳感網(wǎng)絡(luò)負(fù)載均衡路由協(xié)議。該協(xié)議將節(jié)點(diǎn)可用能量、路由跳數(shù)和節(jié)點(diǎn)之間物理距離等參數(shù)引入到路由選擇函數(shù)中，以實(shí)現(xiàn)最優(yōu)路徑的建立，實(shí)現(xiàn)了對無線傳感器網(wǎng)絡(luò)性能的綜合優(yōu)化，并采用了功率控制技術(shù)，有效地提高了數(shù)據(jù)傳輸過程中的能量效率，達(dá)到網(wǎng)絡(luò)整體性能優(yōu)化。通過仿真實(shí)驗(yàn)，證明了本文提出的優(yōu)化算法與傳統(tǒng)定向擴(kuò)散算法相比，在平衡網(wǎng)絡(luò)能量消耗和延長網(wǎng)絡(luò)生存期方面更優(yōu)。下一步工作可以圍繞路由協(xié)議的服務(wù)質(zhì)量支持和降低算法的復(fù)雜度來開展，在降低能量消耗和服務(wù)質(zhì)量間達(dá)到平衡，實(shí)現(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] 馮維. 基于離子群算法求解多目標(biāo)函數(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è)計(jì)研究[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] 陳樂瑞, 孔金生. 基于改進(jìn)遺傳算法的網(wǎng)絡(luò)路由優(yōu)化研究[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2013, 30(4): 135-137.

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

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

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

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

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

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

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

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

[15] 任建華，李元誠，楊洪. 基于路徑寬度的Zigbee網(wǎng)絡(luò)路由算法優(yōu)化[J]. 計(jì)算機(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é)校省級自然科研項(xiàng)目(KJ2013B090)。

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

時(shí)間：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