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

一種基于能量效率的自組織網(wǎng)絡(luò)節(jié)點合作方法

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

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

針對移動自組織網(wǎng)絡(luò)中的節(jié)點自私性問題，以無線網(wǎng)絡(luò)環(huán)境中的拓撲控制和數(shù)據(jù)包轉(zhuǎn)發(fā)作為網(wǎng)絡(luò)節(jié)點的策略空間，并結(jié)合網(wǎng)絡(luò)節(jié)點的能量效率水平，建立了一個基于嚴格位勢博弈的網(wǎng)絡(luò)節(jié)點合作模型。仿真結(jié)果表明，該模型不但滿足了自組織網(wǎng)絡(luò)環(huán)境下的網(wǎng)絡(luò)連通性需求，并且通過節(jié)點間的合作機制降低了網(wǎng)絡(luò)能耗，提高了網(wǎng)絡(luò)節(jié)點的能量效率水平，以及數(shù)據(jù)傳輸?shù)目煽啃院托省?/p>

移動自組織網(wǎng)絡(luò)；網(wǎng)絡(luò)節(jié)點合作；能量效率；拓撲控制；嚴格位勢博弈

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

0 引言

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

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

1 網(wǎng)絡(luò)模型及問題描述

1.1 網(wǎng)絡(luò)模型

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

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

由此可見，該網(wǎng)絡(luò)模型最優(yōu)情況下的網(wǎng)絡(luò)為Gmax，即網(wǎng)絡(luò)中的所有節(jié)點均作為轉(zhuǎn)發(fā)節(jié)點，并且均使用自身許可的最大功率Pmax進行傳輸。

1.2 能量模型

網(wǎng)絡(luò)節(jié)點的能量損耗取決于其建立網(wǎng)絡(luò)連接時所選擇的功率等級，而功率等級又決定了該節(jié)點的傳輸范圍和鄰居節(jié)點集合。從數(shù)據(jù)傳輸?shù)哪康膩砜?，?jié)點的能量消耗可以劃分為2種類型。

在一定時間區(qū)間內(nèi)，網(wǎng)絡(luò)節(jié)點需要承擔(dān)必要的數(shù)據(jù)傳輸服務(wù)，因此，此類能量消耗為發(fā)送自身數(shù)據(jù)包和轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)包所消耗能量的總和。如果令λi表示節(jié)點i的平均通信發(fā)生率，λf為其數(shù)據(jù)包轉(zhuǎn)發(fā)率，則網(wǎng)絡(luò)節(jié)點i的數(shù)據(jù)傳輸能量消耗為：

式中，F(xiàn)i為該節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)策略。

此外，假定網(wǎng)絡(luò)中所有節(jié)點使用最大功率（標準控制信息發(fā)射功率）發(fā)送控制信息，且控制信息比率為λc，則控制信息的能量消耗為：

1.3 問題描述

根據(jù)上述假設(shè)，維護網(wǎng)絡(luò)拓撲結(jié)構(gòu)的過程包含了2個主要目標：①在保證網(wǎng)絡(luò)性能優(yōu)化需求（如連通性及能效）的同時，節(jié)點選擇適當(dāng)?shù)墓β实燃?；②為維護網(wǎng)絡(luò)的連通性能及數(shù)據(jù)轉(zhuǎn)發(fā)需求，確定網(wǎng)絡(luò)節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)策略，即為所確定的合作節(jié)點承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)，而拒絕不合作節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)請求。因此，需要提供一個定義良好的博弈模型，促使所有的網(wǎng)絡(luò)節(jié)點在數(shù)據(jù)包轉(zhuǎn)發(fā)和拓撲控制方面參與網(wǎng)絡(luò)的合作。

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

③每一個參與者i∈N，都有一個二維效用函數(shù)ui（P，F(xiàn)）：A→R來確定節(jié)點自身在博弈過程中的收益或優(yōu)先權(quán)。

節(jié)點的效用函數(shù)為：

式中，αi=f（eti（pi，F(xiàn)i））∈R為與網(wǎng)絡(luò)節(jié)點能量消耗相關(guān)的權(quán)重標量；Gi（P，F(xiàn)）為當(dāng)前所有節(jié)點選定策略后所形成的網(wǎng)絡(luò)拓撲；CN（P，F(xiàn)）為當(dāng)前所有節(jié)點選定策略后該節(jié)點的合作節(jié)點集合，即愿意為其提供數(shù)據(jù)轉(zhuǎn)發(fā)的節(jié)點的集合。

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

2 基于能量效率的網(wǎng)絡(luò)節(jié)點合作算法（BENC）

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

2.1 準備階段

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

2.2 自調(diào)整階段

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

2.3 穩(wěn)定階段

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

3 仿真結(jié)果分析

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

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

圖1　網(wǎng)絡(luò)初始拓撲結(jié)構(gòu)

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

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

圖2　BENC算法的納什均衡結(jié)果

接下來對3種模型的能量效率水平進行比較，在500 s仿真時間內(nèi)，對網(wǎng)絡(luò)中所有節(jié)點進行數(shù)據(jù)包傳輸所消耗的能量進行了檢驗，規(guī)定數(shù)據(jù)包被丟棄之前需要被重新轉(zhuǎn)發(fā)3次，并且重新轉(zhuǎn)發(fā)的消耗也計入到網(wǎng)絡(luò)的總能耗中。在相同拓撲結(jié)構(gòu)下運行50次仿真后得到的結(jié)果如圖4所示。

圖3　數(shù)據(jù)包遞交率

圖4　網(wǎng)絡(luò)能量消耗

由圖4可以看出，由于BENC模型具有拓撲結(jié)構(gòu)優(yōu)化的節(jié)點合作有效路徑，因而顯著降低了數(shù)據(jù)包轉(zhuǎn)發(fā)過程中的能耗，此外，這樣的BENC模型進一步增強了路徑的可靠性和更高的數(shù)據(jù)包投遞率。

4 結(jié)束語

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

［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］ 劉 剛，郭建立，崔 剛，等.移動自組織網(wǎng)絡(luò)環(huán)境中負載均衡策略研究［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

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

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

郭建立 男，（1980—），博士，高級工程師。主要研究方向：云計算、物聯(lián)網(wǎng)和移動自組織網(wǎng)絡(luò)等。