一種基于能量效率的自組織網絡節點合作方法

楊國瑞，郭建立，劉 剛，高莎莎

一種基于能量效率的自組織網絡節點合作方法

楊國瑞1，郭建立1，劉 剛2，高莎莎2

（1.中國電子科技集團公司第五十四研究所，河北石家莊050081；2.燕山大學河北省測試計量技術及儀器重點實驗室，河北秦皇島066004）

針對移動自組織網絡中的節點自私性問題，以無線網絡環境中的拓撲控制和數據包轉發作為網絡節點的策略空間，并結合網絡節點的能量效率水平，建立了一個基于嚴格位勢博弈的網絡節點合作模型。仿真結果表明，該模型不但滿足了自組織網絡環境下的網絡連通性需求，并且通過節點間的合作機制降低了網絡能耗，提高了網絡節點的能量效率水平，以及數據傳輸的可靠性和效率。

移動自組織網絡；網絡節點合作；能量效率；拓撲控制；嚴格位勢博弈

引用格式：楊國瑞，郭建立，劉 剛，等.一種基于能量效率的自組織網絡節點合作方法［J］.無線電工程，2016，46（5）：5-8.

0 引言

在移動自組織網絡（Mobile Ad hoc Network）中，移動節點出于自身資源消耗、延長生命周期考慮，可能拒絕為網絡中其他節點轉發數據，這種行為嚴重影響了網絡性能。Marti［1］的研究結果表明，如果網絡中存在10%～40%的自私節點，將導致網絡平均性能下降16%～32%。目前，研究人員已經提出了一些探索性的思路和方法，采取預設的措施“迫使”或“激勵”網絡節點之間進行合作，以保證網絡的基本需求和整體性能。總體上，所提出的方法可以分為3類：基于信譽的方法、基于貨幣的方法和基于博弈的方法。

基于信譽方法［2-3］根據節點的行為特征建立信譽信息，并在路由和數據轉發過程中根據信譽信息對低信譽值節點（不合作節點）實行懲罰，以此來“迫使”其參與網絡合作。而基于貨幣的方法［4-5］引入了經濟學概念，將數據包轉發作為網絡服務，即源節點使用該服務需要付費，轉發節點提供服務獲得補償，以激勵節點參與網絡合作。此外，還可根據網絡節點固有的自主特性和分布式的操作特點，利用博弈論方法對節點進行形式化建模與分析［6-7］，并且結合網絡節點行為分析［8］、能效公平［9-10］以及控制負載抑制［11-12］等策略，更加全面地提高網絡節點合作方法的有效性和實用性。本文基于博弈論方法，以拓撲控制和數據包轉發作為節點的策略空間，并結合節點的能量效率水平，通過建立一個基于嚴格位勢博弈的節點合作模型，能夠在充分保證移動自組織網絡連通性的同時，提高網絡的能量效率水平。

1 網絡模型及問題描述

1.1 網絡模型

假定移動自組織網絡由一組采用全向天線的移動無線節點組成，網絡中的所有節點均具有調整自身發射功率的能力，可以將其實際發射功率調整到比其最大值低的功率等級，以節省自身的能量消耗，因此，可以將網絡拓撲結構建模為G=（N，E，Ω），其中N是節點集合，包含n個網絡節點，E?N×N是一組具有雙向連接的傳輸鏈路。權值矩陣Ω描述各連接鏈路的相關特性，如增益損失和信噪比等。為簡單起見，本文假設連接的權值同建立這個連接的發射功率等級成正比。為了建立一個有效鏈接，發射功率等級需要與節點間的歐幾里德距離相對應，即如果P（i）=pi≥ωij，并且P（j）=pj≥ωij，則在節點i和j之間存在一個有效的網絡鏈接，其中P=（p1，…，pn）為當前節點功率水平向量。

此外，模型中的每個節點都將網絡中的節點劃分為2個子集，即愿意為其提供轉發數據包的節點集合C以及拒絕為其轉發數據包的節點集合S，為方便起見，可以將節點自身視為其轉發節點，即有C∪S=N。因此得到數據轉發策略向量Fi=（f1，…，fn），其中

由此可見，該網絡模型最優情況下的網絡為Gmax，即網絡中的所有節點均作為轉發節點，并且均使用自身許可的最大功率Pmax進行傳輸。

1.2 能量模型

網絡節點的能量損耗取決于其建立網絡連接時所選擇的功率等級，而功率等級又決定了該節點的傳輸范圍和鄰居節點集合。從數據傳輸的目的來看，節點的能量消耗可以劃分為2種類型。

在一定時間區間內，網絡節點需要承擔必要的數據傳輸服務，因此，此類能量消耗為發送自身數據包和轉發其他節點的數據包所消耗能量的總和。如果令λi表示節點i的平均通信發生率，λf為其數據包轉發率，則網絡節點i的數據傳輸能量消耗為：

式中，Fi為該節點的數據轉發策略。

此外，假定網絡中所有節點使用最大功率（標準控制信息發射功率）發送控制信息，且控制信息比率為λc，則控制信息的能量消耗為：

1.3 問題描述

根據上述假設，維護網絡拓撲結構的過程包含了2個主要目標：①在保證網絡性能優化需求（如連通性及能效）的同時，節點選擇適當的功率等級；②為維護網絡的連通性能及數據轉發需求，確定網絡節點的數據轉發策略，即為所確定的合作節點承擔數據轉發服務，而拒絕不合作節點的數據轉發請求。因此，需要提供一個定義良好的博弈模型，促使所有的網絡節點在數據包轉發和拓撲控制方面參與網絡的合作。

定義博弈Γ=＜N，A，u＞如下：

③每一個參與者i∈N，都有一個二維效用函數ui（P，F）：A→R來確定節點自身在博弈過程中的收益或優先權。

節點的效用函數為：

式中，αi=f（eti（pi，Fi））∈R為與網絡節點能量消耗相關的權重標量；Gi（P，F）為當前所有節點選定策略后所形成的網絡拓撲；CN（P，F）為當前所有節點選定策略后該節點的合作節點集合，即愿意為其提供數據轉發的節點的集合。

由式（5）可見，當所有網絡節點確定其自身的行動策略（Pi，Fi）之后，所有節點得到的有效網絡拓撲收益Gi（P，F）完全相同，而CN（P，F）收益與網絡節點i自身的策略選擇完全無關，即完全依賴于其他網絡節點的策略選擇。因此可知該博弈符合嚴格位勢博弈的定義，是一個加權Coordination-Dummy博弈。同時，根據嚴格位勢博弈的性質，可以確定該博弈具備有限改善路徑特性，且當網絡節點以自私（理性）的方式進行策略抉擇時，能夠收斂到一個穩定的納什均衡。

2 基于能量效率的網絡節點合作算法（BENC）

基于構建的節點博弈模型，為了在存在自私節點的情況下形成有效的拓撲結構，提出了基于能量效率的網絡節點合作算法。算法中，節點根據最佳響應過程，調整其傳輸功率等級以及轉發策略。一個完整的博弈過程包括2個間隔周期，在算法執行階段，通過指定功率級和節點的轉發策略來確定拓撲結構；在數據轉發階段，路由選擇和數據轉發將會在指定拓撲G（P，F）之后被執行，基于功率矢量P=（p1，…，pn）和轉發策略矢量 F=（f1，…，fn）。該算法由3階段組成：準備階段、自調整階段和穩定階段。

2.1 準備階段

在準備階段，網絡中的每個節點都用其自身的最大傳輸功率（Pmaxi）傳輸一個標準的控制信標，并通過搜集鄰居節點的應答信息，確定其最新的鄰居節點集合。在該階段結束時，每個節點都將得到一個最新的相鄰節點列表，其中包括鄰居節點所要求達到每個節點所需要的功率信息，網絡中所有鄰居節點的集合就構成了當前網絡的初始拓撲結構Gmax。

2.2 自調整階段

在自調整階段，節點基于自身的能量水平和效用函數來確定它們將選擇的傳輸功率等級和轉發策略。假定在某一時間點，只允許一個網絡節點基于自身的優先權具備調整其自身參與網絡合作策略的權力。每一次博弈的重復過程都被視為一個普通的標準型博弈，其中每個節點的目標都是選擇最大化其效用的策略，這個不斷重復的過程導致了網絡動態的發展變化。在該過程中，無論何時節點更新自身的策略選擇，它基于式（6）進行自身的策略修正：

2.3 穩定階段

由于采用的博弈模型是一個嚴格位勢博弈，其自身特性保證了納什均衡的存在性，無論何時，當一個網絡節點在自適應階段選擇了一個功率等級及轉發策略，這個選擇將直接影響到其當前的鄰居節點集合，進而可能導致網絡整體拓撲結構的改變。節點在當前的拓撲中更新自身的功率等級和轉發策略后，需要及時廣播這些策略信息。其他網絡節點接收這些控制信息，更新各自的鄰居集合。反之，其他網絡節點根據網絡環境的變化，選擇一個相應的功率等級和轉發策略，響應網絡拓撲的變化和其他節點的策略選擇，以提高其自身的效用。如果沒有任何一個節點需要更新其策略，則意味著算法已經收斂到一個穩定狀態（納什均衡），而嚴格位勢博弈的特性保證了納什均衡的存在。因此，算法在多次迭代之后能夠收斂到一個穩定的納什均衡。

3 仿真結果分析

為了驗證所提出的網絡節點合作模型的有效性，在Matlab中實現了基于拓撲控制和數據轉發的節點合作算法。在仿真試驗中，所有移動自組織網絡節點被均勻地分布到一個1 000m*1 000m的有限區域內。并且規定，為了建立一個有效的傳輸鏈接ij，需要滿足的能量條件為ωij=pij=d2ij，其中dij為節點i和節點j的歐幾里德距離。

仿真條件下移動自組織網絡的初始拓撲Gmax，包含50個節點，每個節點在此階段所采用的標準（最大）傳輸功率均為Pmaxi=100 mW，并且保證初始網絡拓撲結構是連通的，如圖1所示。

圖1　網絡初始拓撲結構

基于圖1的原始拓撲結構，網絡節點根據當前的能量水平調整其自身策略，更新它們的傳輸功率（在1 mW、5 mW、20 mW、30 mW、50 mW和100 mW中選擇）。執行一次BENC算法后達到納什均衡時，拓撲控制優化過程的結果如圖2所示。由圖2可見，BENC算法能夠在有限的時間范圍內，收斂到一個對網絡模型所定義的連通拓撲結構，并且在網絡中每對節點間存在一個包含多個中繼（合作）節點的有效傳輸路徑。

為了衡量該模型對網絡傳輸性能的影響程度，在模擬仿真實驗中檢驗了網絡中不同節點對之間的25個并發信息流的數據傳輸情況，結果如圖3所示，通過與文獻［8-9］所提出算法在相同網絡環境參數情況下的對比可以發現，相對于上述2種算法，BENC模型的網絡數據包的遞交率更高，這是因為基于BENC模型的網絡節點，為了提高自身的效用，積極參與網絡合作是其更優的決策策略。

圖2　BENC算法的納什均衡結果

接下來對3種模型的能量效率水平進行比較，在500 s仿真時間內，對網絡中所有節點進行數據包傳輸所消耗的能量進行了檢驗，規定數據包被丟棄之前需要被重新轉發3次，并且重新轉發的消耗也計入到網絡的總能耗中。在相同拓撲結構下運行50次仿真后得到的結果如圖4所示。

圖3　數據包遞交率

圖4　網絡能量消耗

由圖4可以看出，由于BENC模型具有拓撲結構優化的節點合作有效路徑，因而顯著降低了數據包轉發過程中的能耗，此外，這樣的BENC模型進一步增強了路徑的可靠性和更高的數據包投遞率。

4 結束語

針對移動自組織網絡節點合作問題，本文提出了一種基于能量效率的分布式網絡節點合作方法，該方法將拓撲控制和數據包轉發作為網絡節點的策略空間，并結合節點自身的能量效率水平，構建了一個嚴格位勢博弈節點合作模型。通過Matlab對節點合作模型的有效性進行了驗證，仿真結果表明，該模型不但充分保證了移動自組織網絡的連通性，而且能夠促進節點合作，減少網絡能耗，提高網絡的能量效率水平。

［1］ MARTI S，GIULI T，LAI K，et al.Mitigating Routing Misbehavior in Mobile Ad Hoc Networks［C］∥ Proceedings of the 6th Annual International Conference on Mobile Computing and Networking，2000：255-265.

［2］ JARAMILLO Juan Jose，SRIKANT R.A Game Theory Based Reputation Mechanism to Incentivize Cooperation in Wireless Ad Hoc Networks［J］.Ad Hoc Networks，2010，8（4）：416-429.

［3］ BUCHEGGER S，BOUDEC J Y L.Self-policing Mobile Ad-hoc Networks By Reputation System［J］.IEEE Communications Magazine，2005，43（7）：101-107.

［4］ HE Q，WUD，KHOSLAP.ASecureIncentive Architecture for Ad Hoc Networks［J］.Wireless Communications and Mobile Computing，2006，6（3）：333-346.

［5］ BUTTYAN L，HUBAUX J.Stimulating Cooperation in Self-organizing Mobile Ad Hoc Networks［J］.Mobile Networks and Applications，2003，8（5）：579-592.

［6］ 劉 剛，郭建立，崔 剛，等.移動自組織網絡環境中負載均衡策略研究［J］.無線電工程，2010，40（7）：1-3.

［7］ LI Ze，SHEN Hai-ying.Game-theoretic Analysis of Cooperation Incentive Strategies in Mobile Ad Hoc Networks ［J］.IEEE Transactions on Mobile Computing，2012，11 （8）：1 287-1 303.

［8］ KOMALI R S，MACKENZIE A B，GILLES R P.Effect of SelfishNodeBehavioronEffcientTopologyDesign ［J］.IEEE Transaction on Mobile Computing，2008，7 （9）：1 057-1 069.

［9］ KOMALIR S，MACKENZIE A B.Distributed Topology ControlinAd-HocNetworks：AGameTheoretic Perspective［C］∥Third IEEE Consumer Communication and Networking Conference，2006：563-568.

［10］ZHANG Dan，SHINKUMAR，MANDAYAMNarayan B.Bandwidth Exchange：An Energy Conserving Incentive Mechanism for Cooperation［J］.IEEE Transactions on Wireless Communications，2010，9（6）：2 055-2 065.

［11］KOMALI R S，MACKENZIE A B.Impact of Selfish Packet Forwarding on Energy-efficient Topology Control［C］∥6th International Symposium on IEEE，2008：251-259.

［12］JAVAD Ghaderi，XIE Liang-liang，SHEN Xue-min.Hierarchical Cooperation in Ad Hoc Networks：Optimal Clustering and Achievable Throughput［J］.IEEE Transactions on Information Theory，2009，55（8）：3 425-3 436.

A Cooperation Method of Mobile Ad Hoc Network Nodes Based on Energy Efficiency

YANG Guo-rui1，GUO Jian-li1，LIU Gang2，GAO Sha-sha2
（1.The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China；2.Key Laboratory of Measurement Technology and Instrumentation of Hebei Province，Yanshan University，Qinhuangdao Hebei 066004，China）

Aiming at the selfishness of the nodes in mobile ad hoc networks，a network node cooperative model based on exact potential game model is established by using the wireless network topology controlling and data packets forwarding as the strategy space and depending on the energy efficiency level of network nodes.The simulation results show that this model can not only meet network connectivity requirements under the opening wireless network environment，but also reduce the network energy consumption，improve energy efficiency level of network nodes，and the data transmission reliability and efficiency by network node cooperation in wireless Ad Hoc networks.

mobile ad hoc networks；network node cooperation；energy efficiency；network topology control；exact potential game

TN393

A

1003-3106（2016）05-0005-04

10.3969/j.issn.1003-3106.2016.05.02

2016-01-22

河北省自然科學基金資助項目（F2015203291）；秦皇島市科學技術研究與發展計劃資助項目（201401A037）。

楊國瑞 男，（1972—），高級工程師。主要研究方向：通信網絡總體、移動自組織網絡等。

郭建立 男，（1980—），博士，高級工程師。主要研究方向：云計算、物聯網和移動自組織網絡等。