基于移動—能量代價函數的無線自組織網絡路由策略研究*

劉半藤，周 瑩，陳友榮，王章權

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

基于移動—能量代價函數的無線自組織網絡路由策略研究*

劉半藤1，2*，周 瑩1，陳友榮1，王章權1

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

能量均衡技術一直是無線自組織網絡的熱點研究領域。在深入研究網絡信息傳輸特性的基礎上，提出了一種基于移動—能量代價函數的無線自組織網絡路由策略，并用于網絡信息傳輸。首先，本文考慮節點連通性、能量均衡性，提出了一種節點移動策略;然后，以傳輸路徑節點集合中的瓶頸節點剩余能量、傳輸鏈路數量作為準則，建立以網絡節點為對象的能量代價函數。基于移動—能量代價函數的路由策略從鏈路層的決策轉移到節點層的決策。最后，采用MATLAB數值仿真該路由策略的性能，結果顯示:本文提出的移動—能量代價函數的路由策略既保持了原有路由優化的精度，延遲網絡瓶頸節點能量下降速度，提高網絡生存時間。

能量代價;生存時間;瓶頸節點;動態規劃;路由策略

無線自組織網絡是一種由幾十乃至上百個具有感知、計算和通信能力的可移動節點組成，采用無線通信方式動態組成的對等網絡［1］。近些年，隨著傳感器技術、嵌入式計算技術、通訊技術和計算機網絡技術日趨成熟，使得無線自組織網絡的各種應用逐漸成為可能，成為21世紀信息產業的重要支柱。在無線自組織網絡的各項技術中，路由策略和能量均衡技術一直是該研究領域的關鍵問題，制約著無線自組織網絡的進一步發展，引發了國內外專家學者的廣泛關注。在無線自組織網絡的實際應用中，網絡節點采用電池供電，且通常要求網絡能持續工作幾個月乃至幾年時間。將網絡中第1個節點由于能量耗盡退出網絡的時間定義為網絡生存時間，網絡生存時間是評估無線自組織網性能的最重要指標之一［2－3］。

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

在以上的文獻中，均沒有提到網絡節點的移動性會對網絡能耗所產生的影響。無線自組織網絡中拓撲結構動態變化，節點無序移動性可能造成部分關鍵節點過早退出網絡，也可能使得網絡能量消耗更加均衡。為此，本文在分析網絡節點移動特性的基礎上，提出了一種基于移動—能量代價函數的路由策略。每次信息業務傳輸時，以傳輸路徑節點集合中的瓶頸節點剩余能量、信息鏈路數量作為代價函數，將路由協議中鏈路層的決策轉移到節點層的決策。

1 網絡節點移動策略研究

無線自組織網節點可以自由地在網絡區域內移動，節點的無序移動性使得網絡計算變得更為復雜。因此，本文首先介紹一種節點移動策略，該策略可以提高網絡節點連通性與能量均衡性，同時也可以降低網絡搜索計算量。

假設有N節點隨機地分布于無線自組織網絡區域中，當源節點s向目的節點d發送信息時，考慮信息中的1個比特B。傳輸比特B時，每個節點的坐標可以表示為［xi(B)，yi(B)］， i=1，2，…，N。無線自組織網絡中的每個節點都有1個穩定的通信半徑R［8］。因此，傳輸比特B時，無線自組織網絡的拓撲結構可以用聯通矩陣C=［cij(B)］N×N和距離矩陣D=［dij(B)］N×N進行表述。2個矩陣的元素含義如下:

傳輸比特 B時，節點 i的剩余能量可以用 Ei(B)表示。假設在信息發送間隙，每個節點最大移動距離為L，L可以由網絡內信息發送頻率確定。結合網絡連通性與節點剩余能量，本文提出了一種使用于無線自組織網絡的節點移動策略:①如果網絡中存在孤立節點i(即0)，應該設計一種方法使該節點盡快進入網絡連通區域。首先，尋找網絡節點中與此孤立節點最近的節點

如果dij＜L+R，則可以要求節點i向節點j移動min{L，dij－R}，節點j的移動策略不發生變化。如果dij≥2L+R，則可以要求節點i向節點j移動L，同時考慮節點j是否需要向節點i移動;如果節點j移動后LT上升，則節點j向節點i移動L，否則節點j的移動策略不發生變化。如果L+R＜dij＜2L+R，則可以要求節點i向節點j移動L，同時考慮節點j是否需要向節點i移動;如果節點j移動后LT上升，則節點j向節點i移動dij－R－L，否則節點j的移動策略不發生變化。

注意:即便節點k也是孤立點也沒有關系，節點i和節點k的相互移動會使得兩者不再是孤立點，提高網絡連通性。j。如果dij=mini≠kdik，說明節點j和節點i距離最近。

建立關于網絡連通性的指標LT，用于評價節點i與節點j的相對移動是否會影響原有網絡拓撲結構的連通性。

②對于網絡中的非孤立節點，每個剩余能量高的節點都向節點剩余能量低的方向移動。對于其中的一個非孤立節點i而言，節點i可以感知到與其相鄰節點j的剩余容量，即Ej(B)。尋找到與節點i相鄰、剩余能量最低的節點考慮節點i是否需要向節點k移動。如果節點dik≤L，則可以要求節點i向節點k移動dik，同時節點k向節點i移動dik，形成節點i與節點k的位置互換，并不改變網絡連通性。如果節點dik＞L，考慮節點i與節點k的相互移動是否會影響網絡連通性的指標LT。如果2個節點間相互移動并不影響LT，則可以要求節點i向節點k移動L，同時節點k向節點i移動L;否則，節點i和節點k并不發生移動。

本文所提出的移動策略如圖1所示。

圖1 節點移動策略

2 基于網絡能量代價函數的構造

當源節點s向目的節點d發送信息時，考慮信息中的一個比特B，由中間節點組成的集合中{vi(B)}，剩余能量最小的節點k也就是限制鏈路傳輸時間的關鍵瓶頸節點。節點k的確定過程如下:

動態源路由協議DSR是專家學者們提出的一種適用于無線自組織網絡信息傳輸的路由協議［9］。DSR路由協議的核心思想是以較少的鏈路數為代價將信息從源節點傳輸到目的節點。該思想容易造成網絡中的部分節點由于業務過于繁忙而提早退出網絡，實際的網絡生存時間并不高。考慮瓶頸節點剩余能量Ek(B)的影響，本節提出了一種基于能量代價函數的構造方式。當源節點s向目的節點d發送信息時，每一個中間節點都將選擇能量代價函數最大的相鄰節點進行信息傳輸。節點i能量代價函數fi(B)可以表達如下:

式中:fj(B)表示與節點i相鄰的可用于比特B傳輸的下游節點j的能量代價函數。

為了防止出現多條剩余能量相同的節點，本文以傳輸路徑節點集合中的瓶頸節點剩余生存時間作為第一目標、傳輸鏈路數量作為第二目標。第二目標的函數如下:

式中:hi(B)表示比特B從源節點發送到節點i所經歷的鏈路數量，節點j是節點i的上游節點。

以上述代價函數進行路徑搜索時，以能量代價fi(B)作為主要判別依據，鏈路數量代價hi(B)作為第二指標進行判別。該算法從源節點出發，每個中間節點都尋找下一跳的最優節點，從而將鏈路層的決策轉化為節點層的決策。

該算法采用局部最優的思想降低網絡計算量，但是并未考慮傳輸節點的能量消耗速率。通過式(5)、式(6)進行修正，每個中間節點都需要判斷鏈路的能量消耗速率，并以此作為代價函數進行路徑搜索［10］。因此，基于能量代價函數f*i(B)可以修正如下:

式中:E0表示無線自組織網絡中節點單次發送或者接收數據所消耗的能量，Fi表示節點間兩兩通信一次所消耗的能量。

3 仿真分析

為了深入分析本文提出的基于移動—能量代價函數的路由策略對于無線自組織網絡生存時間、網絡容量產生的影響，本節采用MATLAB軟件對算法進行數值仿真。

在一個300 m×300 m的矩形無線自組織網絡區域內，隨機散布著80個網絡節點，每個節點的通信半徑為50 m。對比網絡節點是否移動兩種策略對于網絡連通性的影響。當網絡節點按照本文所提出的移動策略移動時，網絡連通性隨時間而呈現上升狀態，而當網絡節點處于靜止時網絡的連通性不發生任何變化，即為初始時刻的連通性61%。

假設無線自組織網絡中每個節點的初始剩余能量均與“1”，每個節點在每次處理信息時消耗0.001，不考慮網絡節點移動與待機所產生的影響。采用DSR路由協議，針對節點是否發生移動2種情況，無線自組織網絡瓶頸節點的能量變化如圖3所示。通過圖3可以發現:固定式網絡中可能由于部分核心節點能量消耗過快，而使得網絡生存時間過低。

圖2 本文移動策略下，網絡連通性變化曲線

圖3 2種策略下，網絡瓶頸節點能量變化曲線

對比分析基于移動—能量代價函數的路由策略與DSR路由策略，分析網絡瓶頸節點隨仿真時間的變化趨勢如圖4所示。

圖4 2種路由協議瓶頸節點剩余能量的變化趨勢

通過圖4可以發現:本文提出的基于移動—能量代價函數的路由策略可以有效地降低為網絡瓶頸節點能量下降速率，提高網絡生存時間。

4 結束語

在深入研究網絡節點移動特性的基礎上，本文提出了一種移動—能量代價函數的構造方法，并用于指導網絡信息傳輸。首先，本文基于節點連通性、能量均衡性，提出了一種節點移動策略;然后，以傳輸路徑節點集合中的瓶頸節點剩余能量、傳輸鏈路數量作為準則，建立以網絡節點為對象的能量代價函數。數值仿真結果顯示:本文提出的移動—能量代價函數的路由策略既保持了原有路由優化的精度，也能提高網絡生存時間。

［1］ 劉杰，王玲，王杉，等.基于能量有效的逆向AODV路由協議研究［J］.計算機應用研究，2015，32(6):1849－1851.

［2］ Vrinda Gupta，Rajoo Pandey.An Improved Energy Aware Distributed Unequal Clustering Protocol for Heterogeneous Wireless Sensor Networks［J］.Engineering Science and Technology，an International Journal，Volume 19，Issue 2，June 2016:1050－1058.

［3］ 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.

［4］ 黃浩軍，尹浩，陳和平，等.無線Ad Hoc網絡能量感知地理路由協議研究進展［J］.軟件學報，2014，(5):1061－1084.

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

［6］ 蔣文賢.壓縮感知的能量異構WSN分簇路由協議［J］.傳感技術學報，2013，26(6):894－900.

［7］ Fatih Deniz，Hakki Bagci，Ibrahim Korpeoglu，et al.An Adaptive，Energy-Aware and Distributed Fault-Tolerant Topology-Control Algorithm for Heterogeneous Wireless Sensor Networks［J］.Ad Hoc Networks，2016，44:104－117.

［8］ 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.

［9］ Huang Gaofei，Tu Wanqing.Optimal Resource Allocation in Wireless-Powered OFDM Relay Networks［J］.Computer Networks，2016，104: 94－107.

［10］Zhao Feng，Wei Lina，Chen Hongbin.Optimal Time Allocation for Multi-Antenna Wireless Powered Heterogeneous Sensor Network Communications under Imperfect CSI［J］.Signal Processing，2016，126:159－164.

劉半藤(1984－)，男，漢族，杭州余姚人，工科碩士，講師，主要研究方向為無線傳感網絡，信息融合技術，hupo3@ sina.com。

Research on the Routing Algorithm in MANETs Based on the Energy Cost Function*

LIU Benteng1，2*，ZHOU Ying1，CHEN Yourong1，WANG Zhangquan1
(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)

The energy balance technology is a hot research field of the wireless selforganizing network.After the further study of the network information transmission characteristics，a kind of wireless selforganized network routing strategy used for network information transmission is proposed based on mobile-energy cost function.At first，considering the node connectivity and energy balance，a node mobile strategy is carried out;then a energy cost function is designed With residual energy of transmission path bottleneck nodes and transmission link number as criterion，and the routing strategy is determined in node layer instead of link layer;at last，the numerical simulation is performed on MATLAB，the result shows the routing strategy proposed keep the original optimal routing precision，delay the network bottleneck node energy falling speed and improve the network survival time.

energy cost;survival life;bottleneck node;dynamic programming;routing strategy

TP393

A

1004－1699(2017)02－0302－04

C:7230

10.3969/j.issn.1004－1699.2017.02.023

項目來源:浙江省自然科學基金項目(LY15F030004);國家自然科學基金項目(61501403);浙江省公益性技術應用研究計劃項目(2016C33038);浙江樹人大學校級科研項目(2104A11001)

2016－06－11 修改日期:2016－10－27