基于加權(quán)路由思想的無線自組織網(wǎng)絡(luò)生存時(shí)間優(yōu)化算法研究*

劉半藤,周 瑩,陳友榮

(1.浙江樹人大學(xué)信息科技學(xué)院,杭州 310015;2.浙江大學(xué)控制學(xué)院,杭州 310058)

?

基于加權(quán)路由思想的無線自組織網(wǎng)絡(luò)生存時(shí)間優(yōu)化算法研究*

劉半藤1,2*,周 瑩1,陳友榮1

(1.浙江樹人大學(xué)信息科技學(xué)院,杭州 310015;2.浙江大學(xué)控制學(xué)院,杭州 310058)

在無線自組織網(wǎng)絡(luò)中,網(wǎng)絡(luò)生存時(shí)間是衡量網(wǎng)絡(luò)性能的重要指標(biāo)之一。分析影響網(wǎng)絡(luò)生存時(shí)間的眾多因素后,提出了一種工作量加權(quán)路由模型以提高無線自組織網(wǎng)絡(luò)的生存時(shí)間。在網(wǎng)絡(luò)信息傳輸?shù)倪^程中,綜合每條鏈路的業(yè)務(wù)工作量對網(wǎng)絡(luò)鏈路進(jìn)行加權(quán),建立距離加權(quán)傳輸數(shù)學(xué)模型。該模型通過降低工作較為繁忙節(jié)點(diǎn)的信息轉(zhuǎn)發(fā)概率,從而到達(dá)均衡節(jié)點(diǎn)能耗的目的。最后,采用MATLAB進(jìn)行數(shù)值仿真,結(jié)果顯示本文提出的路由算法可以有效延遲網(wǎng)絡(luò)生存時(shí)間,均衡網(wǎng)絡(luò)節(jié)點(diǎn)的能耗。

生存時(shí)間;瓶頸節(jié)點(diǎn);路由策略

無線自組織網(wǎng)絡(luò)是一種不需要固定設(shè)備支持的新型無線通信網(wǎng)絡(luò)。網(wǎng)絡(luò)中各節(jié)點(diǎn)即用戶終端自行組網(wǎng),非鄰接兩節(jié)點(diǎn)間的通信依靠其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)實(shí)現(xiàn),從而組成一個(gè)多跳無線網(wǎng)絡(luò)。由于無線自組織網(wǎng)絡(luò)具有高度的靈活性、抗毀性等,使得無線自組織網(wǎng)絡(luò)在搶險(xiǎn)救災(zāi)、戰(zhàn)場監(jiān)控、環(huán)境監(jiān)測、醫(yī)療衛(wèi)生等領(lǐng)域具有重要的實(shí)用價(jià)值和廣闊的應(yīng)用前景[1]。由于無線自組織網(wǎng)絡(luò)中的節(jié)點(diǎn)通常采用電池來供應(yīng)能量。在實(shí)際應(yīng)用中,節(jié)點(diǎn)電源在一段時(shí)間內(nèi)不可更新,從而使得網(wǎng)絡(luò)的生存時(shí)間與節(jié)點(diǎn)的能量消耗密切相關(guān)。因此,設(shè)計(jì)一種算法均衡整個(gè)網(wǎng)絡(luò)能量消耗,延長網(wǎng)絡(luò)生存時(shí)間顯得至關(guān)重要。文獻(xiàn)[2]提出,可以將網(wǎng)絡(luò)生存時(shí)間定義為從網(wǎng)絡(luò)初始時(shí)刻開始到網(wǎng)絡(luò)中第1個(gè)節(jié)點(diǎn)由于能量耗盡退出網(wǎng)絡(luò)時(shí)刻為止所經(jīng)歷的時(shí)間。文獻(xiàn)[3]中,作者指出網(wǎng)絡(luò)能耗與網(wǎng)絡(luò)路由策略息息相關(guān),通過恰當(dāng)?shù)卦O(shè)置路由策略搜索準(zhǔn)則可以降低網(wǎng)絡(luò)能耗,提高網(wǎng)絡(luò)生存時(shí)間。

近年來,國內(nèi)外專家學(xué)者針對能量路由開展了廣泛的研究。如文獻(xiàn)[4]中,作者提出了一種基于最小傳送能量的路由算法。該算法選擇具有最小傳輸能量消耗的路徑將數(shù)據(jù)包從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn),這種算法具有較好的能量有效性。但是由于能量有效的路徑上承擔(dān)過大的負(fù)載,容易造成能量有效的路由路徑提前死亡,從而其網(wǎng)絡(luò)生存時(shí)間并不高。文獻(xiàn)[5]中,作者提出了一種的能量均衡路由協(xié)議。在該協(xié)議中,通過在剩余能量大于某一閾值的節(jié)點(diǎn)集合中選擇具有最小傳輸能量消耗的節(jié)點(diǎn)作為信息傳輸?shù)南乱惶?jié)點(diǎn)。這樣可以平衡整個(gè)網(wǎng)絡(luò)的能量傳輸消耗,避免最短路由上的節(jié)點(diǎn)過早消耗盡能量,以實(shí)現(xiàn)一定程度上的能量消耗均衡性。文獻(xiàn)[6]中,作者提出了一種圖論算法,該算法試圖通過計(jì)算每一條路由的剩余能量水平,然后排除任何剩余能量水平高于最低能量路徑若干倍的路由,由于算法的性能取決于依靠經(jīng)驗(yàn)參數(shù),因此算法并不能總是給出最優(yōu)的解決方案。文獻(xiàn)[7]中,針對網(wǎng)絡(luò)中某些關(guān)鍵節(jié)點(diǎn)過度消耗能量,致使網(wǎng)絡(luò)節(jié)點(diǎn)能耗分布不均,影響網(wǎng)絡(luò)的性能的缺陷,提出了一種基于博弈論的均衡路由協(xié)議,設(shè)計(jì)基于可靠度和節(jié)點(diǎn)的剩余能量的選擇路徑,解決節(jié)點(diǎn)能耗不均的問題,同時(shí)鼓勵(lì)節(jié)點(diǎn)參與協(xié)作。實(shí)驗(yàn)結(jié)果表明,該協(xié)議提高了節(jié)點(diǎn)能量的利用率和節(jié)點(diǎn)生存時(shí)間,提高了網(wǎng)絡(luò)的穩(wěn)定性。分析現(xiàn)有節(jié)能方法存在的不足之處,本文提出了一種工作量加權(quán)路由模型以提高無線自組織網(wǎng)絡(luò)的生存時(shí)間。

1 網(wǎng)絡(luò)節(jié)點(diǎn)業(yè)務(wù)量均衡的優(yōu)化模型

(1)

(2)

因此,傳輸矩陣和連通矩陣之間需要滿足如下關(guān)系:

C≥X

(3)

假設(shè)無線自組織網(wǎng)絡(luò)中,業(yè)務(wù)通信隨機(jī)產(chǎn)生。每個(gè)源節(jié)點(diǎn)都可以隨機(jī)地挑選網(wǎng)絡(luò)中的其他節(jié)點(diǎn)作為信息發(fā)送的目的節(jié)點(diǎn)。因此,本文采用期望的方式計(jì)算網(wǎng)絡(luò)生存時(shí)間。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)兩兩之間需要通信時(shí),節(jié)點(diǎn)i的工作量ti計(jì)算方式如下:

(4)

為了盡量延長無線自組織網(wǎng)絡(luò)的生存時(shí)間,則將工作量最多的節(jié)點(diǎn)進(jìn)行優(yōu)化,最優(yōu)化數(shù)學(xué)模型可表示為[9]:

Z=minmaxti

(5)

由圖論知識(shí)[10]可知:在一次信息傳輸過程中,源節(jié)點(diǎn)只發(fā)送一次信息,目的節(jié)點(diǎn)只接受一次信息,而每個(gè)中間節(jié)點(diǎn)需要轉(zhuǎn)發(fā)一次信息。于是,可得到如下約束條件:

(6)

綜上所述,無線自組織網(wǎng)絡(luò)的最長生存時(shí)間數(shù)學(xué)模型整理如下:

(7)

該模型充分考慮到要均衡一個(gè)全過程中各節(jié)點(diǎn)的工作量,求解該模型可得到最優(yōu)網(wǎng)絡(luò)信息傳輸方案(即X=(xij)N×N)。但是,對于每一對給定源節(jié)點(diǎn)和目的節(jié)點(diǎn),需要檢索所有路徑導(dǎo)致該模型的計(jì)算量龐大,無法在短時(shí)間內(nèi)求解[11]。因此,本文基于該模型的分析過程,考慮網(wǎng)絡(luò)加權(quán)路由模型,以求在模型計(jì)算量上有所改進(jìn),使得求解結(jié)果逼近最優(yōu)。

2 網(wǎng)絡(luò)加權(quán)路由數(shù)學(xué)模型

wij(k)=f(ni(k),nj(k),nmax(k))=

(8)

式中:nmax(k)表示在第k次信息發(fā)送過程中,網(wǎng)絡(luò)中所有節(jié)點(diǎn)中的最大值,即:

(9)

由于網(wǎng)絡(luò)生存時(shí)間的限制,要求網(wǎng)絡(luò)中任一節(jié)點(diǎn)的狀態(tài)k≤K。ni(k)可以由以下遞推式關(guān)系式得到:

(10)

因此,從源節(jié)點(diǎn)s向目的節(jié)點(diǎn)d的加權(quán)距離路由模型如下:

(11)

3 仿真分析

為了深入分析本文提出的工作量加權(quán)路由算法對于無線自組織網(wǎng)絡(luò)生存時(shí)間產(chǎn)生的影響,本節(jié)采用MATLAB軟件對算法進(jìn)行數(shù)值仿真。在一個(gè)300 m×300 m的矩形無線自組織網(wǎng)絡(luò)區(qū)域內(nèi),隨機(jī)散布著80個(gè)網(wǎng)絡(luò)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)的通信半徑為50 m,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示。采用DSR路由協(xié)議[12],網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的工作量如圖2所示。

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)工作量示意圖

由上圖可知,在DSR路由協(xié)議中各節(jié)點(diǎn)的工作量分布十分不均衡,編號為59的節(jié)點(diǎn)工作量高達(dá)1 511。而生存時(shí)間取決于工作量最大的瓶頸節(jié)點(diǎn),少數(shù)節(jié)點(diǎn)的過度使用對延長網(wǎng)絡(luò)生存時(shí)間是十分不利的。所以,DSR并不是最優(yōu)的無線自組織網(wǎng)絡(luò)路由模型。在無線自組織網(wǎng)絡(luò)中,網(wǎng)絡(luò)的生存時(shí)間才是關(guān)鍵。然而在DSR模型中,存在過度地選擇 最短的路徑傳輸數(shù)據(jù),導(dǎo)致該路徑能量消耗過快,最終造成某些節(jié)點(diǎn)過早失效使得網(wǎng)絡(luò) 癱瘓的情況。由圖3可知,當(dāng)β=0.99時(shí),結(jié)果較為穩(wěn)定。

在按照加權(quán)模型需要選取系數(shù)β的最佳取值,通過對系數(shù)β進(jìn)行靈敏度分析以確定它的取值。借助 MATLAB軟件,按以上求解流程求得與每個(gè)β取值相應(yīng)的單個(gè)節(jié)點(diǎn)最大工作量,結(jié)果如圖3所示。

圖3 β靈敏度分析示意圖

圖4 兩種算法的瓶頸節(jié)點(diǎn)能量變化圖

假設(shè)無線自組織網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的初始剩余能量均與“1”,每個(gè)節(jié)點(diǎn)在每次處理信息時(shí)消耗0.001。無線自組織網(wǎng)絡(luò)節(jié)點(diǎn)兩兩之間通信時(shí),網(wǎng)絡(luò)瓶頸節(jié)點(diǎn)的能量變化如圖4所示,網(wǎng)絡(luò)中節(jié)點(diǎn)工作量分布狀況如圖5所示。

圖5 兩種算法工作量變化圖

由圖4、圖5可以發(fā)現(xiàn),基于工作量加權(quán)的路由算法可以有效地降低瓶頸節(jié)點(diǎn)工作量,延長網(wǎng)絡(luò)生存時(shí)間。

4 結(jié)束語

分析影響網(wǎng)絡(luò)生存時(shí)間的眾多因素后,本文提出了一種工作量加權(quán)路由模型以提高無線自組織網(wǎng)絡(luò)的生存時(shí)間。在網(wǎng)絡(luò)信息傳輸?shù)倪^程中,綜合每條鏈路的業(yè)務(wù)工作量對網(wǎng)絡(luò)鏈路進(jìn)行加權(quán),建立最小代價(jià)傳輸數(shù)學(xué)模型。該模型通過降低工作較為繁忙節(jié)點(diǎn)的信息轉(zhuǎn)發(fā)概率,從而到達(dá)均衡節(jié)點(diǎn)能耗、延長網(wǎng)絡(luò)生存時(shí)間的目的。

[1] Chirihane G,Zibouda A,Mohamed B. An Adaptive Clustering Approach to Dynamic Load Balancing and Energy Efficiency in Wireless Sensor Networks[J]. Energy,2016,114(1):647-662.

[2] Miguel S,Javier G,Baldomero C P. Multipath QoS-Driven Routing Protocol for Industrial Wireless Networks[J]. Journal of Network

and Computer Applications,2016,74:121-132.

[3] Vrinda G,Rajoo P. An Improved Energy Aware Distributed Unequal Clustering Protocol for Heterogeneous Wireless Sensor Networks[J]. Engineering Science and Technology,an International Journal,2016,19(2):1050-1058.

[4] Zhang Deyu,Chen Zhigang,Zhou Haibo,et al. Energy-Balanced Cooperative Transmission Based on Relay Selection and Power Control in Energy Harvesting Wireless Sensor Network[J]. Computer Networks,2016,104(20):189-197.

[5] 黃浩軍,尹浩,陳和平,等. 無線Ad Hoc網(wǎng)絡(luò)能量感知地理路由協(xié)議研究進(jìn)展[J]. 軟件學(xué)報(bào),2014(5):1061-1084.

[6] 彭鐸,黎鎖平,楊喜娟,等. 一種能量高效的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J]. 傳感技術(shù)學(xué)報(bào),2014,(12):1687-1691.

[7] 蔣文賢.壓縮感知的能量異構(gòu)WSN分簇路由協(xié)議[J]. 傳感技術(shù)學(xué)報(bào),2013(6):894-900.

[8] Fatih D,Hakki B,Ibrahim K. An Adaptive,Energy-Aware and Distributed Fault-Tolerant Topology-Control Algorithm for Heterogeneous Wireless Sensor Networks. Ad Hoc Networks,2016,44:104-117.

[9] Hao Xiaochen,Liu Weijing,Yao Ning,et al. Distributed Topology Construction Algorithm to Improve Link Quality and Energy Efficiency for Wireless Sensor Networks[J]. Journal of Network and Computer Applications,Available online 22 April,2016.

[10] Huang Gaofei,Tu Wanqing. Optimal Resource Allocation in Wireless-Powered OFDM Relay Networks[J]. Computer Networks,2016,104:94-107.

[11] Zhao Feng,Wei Lina,Chen Hongbin. Optimal Time Allocation for Multi-Antenna Wireless Powered Heterogeneous Sensor Network Communications Under Imperfect CSI. Signal Processing,2016,126:159-164.

[12] 余旭濤,畢光國,王霄峻,等. Ad Hoc網(wǎng)絡(luò)按需路由協(xié)議的改進(jìn)[J]. 計(jì)算機(jī)學(xué)報(bào),2004,27(6):838-844.

劉半藤(1984-),男,漢族,杭州余姚人,工科碩士,講師,主要研究方向?yàn)闊o線傳感網(wǎng)絡(luò),信息融合技術(shù),hupo3@sina.com。

Research on the Routing Algorithm Optimizing Lifetime of Wireless Ad Hoc Networks*

LIUBanteng1,2*,ZHOUYing1,CHENYourong1

(1.College of Information Science and Technology,Zhejiang Shuren University,Hangzhou 310015,China;2.College of Control Science and Engineering,Zhejiang University,Hangzhou 310058,China)

Saving energy has been a hot issue in the field of wireless ad hoc networks. After analyzing the characteristics of network lifetime,this paper proposed a weighted-routing algorithm optimizing lifetime of wireless ad hoc networks. In the process of information transmission,the load of each link was considered to build the optimal model. This algorithm would reduce the transmission probability of the busy link,so as to achieve the balance node energy consumption,prolong the lifetime of the network.

lifetime of network;bottleneck node;routing strategy

項(xiàng)目來源:浙江省自然科學(xué)基金項(xiàng)目(LY15F030004);國家自然科學(xué)基金項(xiàng)目(61501403);浙江省公益性技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目(2016C33038);浙江樹人大學(xué)校級科研項(xiàng)目(2104A11001)

2016-06-12 修改日期:2016-10-24

TP393

A

1004-1699(2017)03-0463-04

C:7230

10.3969/j.issn.1004-1699.2017.03.021