基于加權路由思想的無線自組織網絡生存時間優化算法研究*

劉半藤,周 瑩,陳友榮

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

?

基于加權路由思想的無線自組織網絡生存時間優化算法研究*

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

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

在無線自組織網絡中,網絡生存時間是衡量網絡性能的重要指標之一。分析影響網絡生存時間的眾多因素后,提出了一種工作量加權路由模型以提高無線自組織網絡的生存時間。在網絡信息傳輸的過程中,綜合每條鏈路的業務工作量對網絡鏈路進行加權,建立距離加權傳輸數學模型。該模型通過降低工作較為繁忙節點的信息轉發概率,從而到達均衡節點能耗的目的。最后,采用MATLAB進行數值仿真,結果顯示本文提出的路由算法可以有效延遲網絡生存時間,均衡網絡節點的能耗。

生存時間;瓶頸節點;路由策略

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

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

1 網絡節點業務量均衡的優化模型

(1)

(2)

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

C≥X

(3)

假設無線自組織網絡中,業務通信隨機產生。每個源節點都可以隨機地挑選網絡中的其他節點作為信息發送的目的節點。因此,本文采用期望的方式計算網絡生存時間。當網絡中節點兩兩之間需要通信時,節點i的工作量ti計算方式如下:

(4)

為了盡量延長無線自組織網絡的生存時間,則將工作量最多的節點進行優化,最優化數學模型可表示為[9]:

Z=minmaxti

(5)

由圖論知識[10]可知:在一次信息傳輸過程中,源節點只發送一次信息,目的節點只接受一次信息,而每個中間節點需要轉發一次信息。于是,可得到如下約束條件:

(6)

綜上所述,無線自組織網絡的最長生存時間數學模型整理如下:

(7)

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

2 網絡加權路由數學模型

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

(8)

式中:nmax(k)表示在第k次信息發送過程中,網絡中所有節點中的最大值,即:

(9)

由于網絡生存時間的限制,要求網絡中任一節點的狀態k≤K。ni(k)可以由以下遞推式關系式得到:

(10)

因此,從源節點s向目的節點d的加權距離路由模型如下:

(11)

3 仿真分析

為了深入分析本文提出的工作量加權路由算法對于無線自組織網絡生存時間產生的影響,本節采用MATLAB軟件對算法進行數值仿真。在一個300 m×300 m的矩形無線自組織網絡區域內,隨機散布著80個網絡節點,每個節點的通信半徑為50 m,網絡的拓撲結構如圖1所示。采用DSR路由協議[12],網絡中每個節點的工作量如圖2所示。

圖1 網絡拓撲結構示意圖

圖2 網絡節點工作量示意圖

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

在按照加權模型需要選取系數β的最佳取值,通過對系數β進行靈敏度分析以確定它的取值。借助 MATLAB軟件,按以上求解流程求得與每個β取值相應的單個節點最大工作量,結果如圖3所示。

圖3 β靈敏度分析示意圖

圖4 兩種算法的瓶頸節點能量變化圖

假設無線自組織網絡中每個節點的初始剩余能量均與“1”,每個節點在每次處理信息時消耗0.001。無線自組織網絡節點兩兩之間通信時,網絡瓶頸節點的能量變化如圖4所示,網絡中節點工作量分布狀況如圖5所示。

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

由圖4、圖5可以發現,基于工作量加權的路由算法可以有效地降低瓶頸節點工作量,延長網絡生存時間。

4 結束語

分析影響網絡生存時間的眾多因素后,本文提出了一種工作量加權路由模型以提高無線自組織網絡的生存時間。在網絡信息傳輸的過程中,綜合每條鏈路的業務工作量對網絡鏈路進行加權,建立最小代價傳輸數學模型。該模型通過降低工作較為繁忙節點的信息轉發概率,從而到達均衡節點能耗、延長網絡生存時間的目的。

[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網絡能量感知地理路由協議研究進展[J]. 軟件學報,2014(5):1061-1084.

[6] 彭鐸,黎鎖平,楊喜娟,等. 一種能量高效的無線傳感器網絡非均勻分簇路由協議[J]. 傳感技術學報,2014,(12):1687-1691.

[7] 蔣文賢.壓縮感知的能量異構WSN分簇路由協議[J]. 傳感技術學報,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網絡按需路由協議的改進[J]. 計算機學報,2004,27(6):838-844.

劉半藤(1984-),男,漢族,杭州余姚人,工科碩士,講師,主要研究方向為無線傳感網絡,信息融合技術,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

項目來源:浙江省自然科學基金項目(LY15F030004);國家自然科學基金項目(61501403);浙江省公益性技術應用研究計劃項目(2016C33038);浙江樹人大學校級科研項目(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