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

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

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

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

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

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

能量代價;生存時間;瓶頸節(jié)點;動態(tài)規(guī)劃;路由策略

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

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

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

1 網絡節(jié)點移動策略研究

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

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

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

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

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

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

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

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

圖1 節(jié)點移動策略

2 基于網絡能量代價函數(shù)的構造

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

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

式中:fj(B)表示與節(jié)點i相鄰的可用于比特B傳輸?shù)南掠喂?jié)點j的能量代價函數(shù)。

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

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

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

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

式中:E0表示無線自組織網絡中節(jié)點單次發(fā)送或者接收數(shù)據(jù)所消耗的能量，F(xiàn)i表示節(jié)點間兩兩通信一次所消耗的能量。

3 仿真分析

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

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

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

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

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

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

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

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

4 結束語

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

［1］ 劉杰，王玲，王杉，等.基于能量有效的逆向AODV路由協(xié)議研究［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網絡能量感知地理路由協(xié)議研究進展［J］.軟件學報，2014，(5):1061－1084.

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

［6］ 蔣文賢.壓縮感知的能量異構WSN分簇路由協(xié)議［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