王 宏**,2，李建華，崔 瓊

(1.空軍工程大學 信息與導航學院，西安 710077；2.國防科技大學 信息通信學院，西安 710106)

基于博弈論的無線自組網動態(tài)接入激勵機制*

王 宏**1,2，李建華1，崔 瓊1

(1.空軍工程大學 信息與導航學院，西安 710077；2.國防科技大學 信息通信學院，西安 710106)

無線自組網節(jié)點的能量有限導致網內節(jié)點往往拒絕承擔新節(jié)點入網所帶來的認證負荷。為激勵無線自組網節(jié)點參與新節(jié)點的入網認證，引入博弈論的公共物品供給博弈理論和維克里-克拉克-格羅夫斯(VCG)機制理論，構建了無線自組網的動態(tài)接入激勵機制。提出了認證節(jié)點選舉辦法，給出了新節(jié)點認證付酬和認證節(jié)點收益函數，分析了認證能量消耗。理論證明了激勵機制具有策略防偽、個體理性和預算平衡3個特性。實例分析了不同參數設置情況下網內節(jié)點就新節(jié)點接入認證、個體與集體的合作博弈過程，結果表明該機制能有效地激勵節(jié)點，為了自身的最大利益積極選擇參與新節(jié)點的入網認證。

無線自組網；接入認證；博弈論；激勵機制

1 引 言

無線自組網是在沒有固定的網絡基礎設施的前提下，移動節(jié)點之間通過無線信道連接構成的動態(tài)拓撲結構的網絡。無線信道的大眾開放性、移動節(jié)點的分布式控制等特征使得無線自組網較傳統(tǒng)網絡面臨更多安全威脅。采取安全高效的認證機制可以有效阻止非法節(jié)點的入侵和攻擊，是提升無線自組網安全性能的關鍵。然而，在無線自組網中各移動節(jié)點大多都是依賴電池等有限源提供能量，處理能力和計算能力有限，已完成組網的、理性的網內節(jié)點往往不肯承擔后入網節(jié)點接入帶來的任務負荷，拒絕耗費自身的能量為他人提供接入認證服務，致使接入訪問呈現整體不合作的“消極”狀態(tài)[1-2]。設計一種科學合理的接入激勵機制，有效促進無線自組網節(jié)點的積極協(xié)作，實現無線自組網的動態(tài)隨遇接入，已經成為無線自組網發(fā)展亟待解決的現實問題。

機制設計是博弈論在社會選擇方面的運用，它將參與者的行為描述為博弈策略，同時按照社會選擇理論對各種情形設定相應的社會目標，研究構造什么樣的博弈形式能使這個博弈的均衡最接近既設的社會目標。假設參與者總會采取使自己獲得最大效用(收益和損失之差)的策略，接入激勵機制設計就是考慮構造什么樣的博弈形式使得參與者既考慮自身能量消耗，也不得不兼顧承擔新節(jié)點的入網認證事務，從而激勵節(jié)點積極參與網絡事務的責任分擔。文獻[3-4]將節(jié)點個體與集體的博弈過程假設為多階段博弈，并引入演化博弈理論，提出了一種針對不愿承擔轉發(fā)分組任務節(jié)點的懲罰機制，使節(jié)點采取合作時的收益永遠大于不合作的收益，從而保證無線自組網的連通性和可用性。文獻[5-9]引入拍賣博弈機制解決帶寬、頻譜等網絡資源的分配問題，調動資源申請者的參與資源競爭的積極性，從而達到網絡資源分配的公平公開。文獻[10]以多Agent系統(tǒng)為平臺，基于動態(tài)無限博弈提出多Agent分工合作機制的模型，促進各個自治系統(tǒng)的相互合作。歸納起來，針對激勵機制設計的研究，一方面主要集中在節(jié)點分組轉發(fā)激勵機制方面，鮮有安全認證機制方面的研究；另一方面，機制設計大多側重于長期使用的無線自組網或無線Mesh網絡，而對于短期或一次性的自組網的機制設計研究較少，這樣的網絡節(jié)點更加關注眼前的既得利益，較長期網絡的節(jié)點表現出更差的合作耐性。因此，有必要針對無線自組網節(jié)點在安全入網認證方面特性，進一步研究接入認證激勵機制。

本文借鑒公共物品供給博弈機制[11](典型代表為“三個和尚沒水喝”“雪堆”博弈)，將懲罰措施引入維克里-克拉克-格羅夫斯(VCG)機制[10]中，用于節(jié)點自由度更大、自主協(xié)同要求更高的無線自組網新節(jié)點入網認證激勵機制設計，調動網內節(jié)點承擔新節(jié)點入網認證的積極性。

2 基于VCG的動態(tài)接入激勵機制

VCG機制是在公共物品有效供給和分配過程中，為激勵具有擬線性偏好[12]的參與者真實地表現對于公共物品的偏好程度而設計的一種機制。為激勵無線自組網內節(jié)點積極響應外來節(jié)點的入網請求，促使節(jié)點真實報告自己的能源、功耗等具體信息。本文將量化的懲罰措施引入VCG機制。首先為每一個節(jié)點分配一個信譽值，信譽值會根據節(jié)點的表現行為動態(tài)變化，當節(jié)點的信譽值低于閾值的時候，鄰居便會拒絕為其提供諸如轉發(fā)數據包等服務，導致其被整個網絡邊緣化。節(jié)點獨立理性地決定其與網絡的合作程度，合作則可以獲得付酬，但提供認證等服務必定有一定的能量消耗，節(jié)點試圖平衡其信譽和能量。

假設某無線自組網中現存(B1,B2,…,Bn)共n個節(jié)點，每個Bi(i=1,2,…,n)有ki種類型，當前有一個等待加入網絡的節(jié)點BNew，本文研究如何調動(B1,B2,…,Bn)積極響應BNew認證申請的激勵機制，首先給出假設條件。

假設1：無線自組網中的節(jié)點除了具有自主性、對等性等特征，還具有趨利避害的理性特征。

假設2：節(jié)點i的剩余能量報告是秘密信息，在其余節(jié)點看來它服從分布函數為Fi(x)，且Fi(x)≥0，概率分布為pi(xi),(i=1,2,…,ki)。

假設3：網內節(jié)點相互獨立，不存在合謀抵制新節(jié)點加入的情況。當新節(jié)點發(fā)出認證請求時，響應節(jié)點的能量消耗報告相互獨立，若節(jié)點i的策略集為Bi，則除i外的其他節(jié)點策略集記為B-i。

假設4：響應節(jié)點的能量消耗報告相同是小概率事件，在文中環(huán)境下不可能發(fā)生。

無線自組網動態(tài)接入激勵機制可記為

VCG:{A,C,R}。

文中符合及其表達意義見表1。

表1 文中符號表達意義Tab.1 Letters and symbols

2.1節(jié)點選舉辦法

動態(tài)接入認證節(jié)點選擇模型為

(1)

2.2新節(jié)點付酬

為了激勵網內節(jié)點參與認證，機制為參與認證的節(jié)點提供付酬，參與節(jié)點i的付酬函數定義為

(2)

2.3認證節(jié)點收益

當參與者具有擬線性偏好特性時，可以使用轉移支付調節(jié)參與者的收益，達到帕累托均衡。下面通過收益函數的設計，使得參與者具有擬線性偏好，從而使用VCG機制激勵節(jié)點積極參與入網節(jié)點的認證。

如果真實能量消耗為ci的節(jié)點i最終被選定，令它的收益函數為

(3)

2.4認證能量消耗

除了認證節(jié)點的付酬、收益函數外，認證節(jié)點i的能量消耗函數ci也是動態(tài)接入激勵機制的重要組成部分。函數ci與自身能量剩余、信譽度有關，按照文獻[8]定義的節(jié)點分類方法，首先引進一套分類標準P={ρ1，ρ2,…,ρl-1}，每個節(jié)點的能量Ei(i=1,2,…,n)與一個級別cli對應：

(4)

3 激勵機制的性能分析

有效的博弈機制必須滿足策略防偽(strategy-proof)、個人理性(individual rational)和預算平衡(budget-balanced)[13]。下面證明當網內節(jié)點能量消耗為秘密信息，節(jié)點之間僅知道其他參與節(jié)點的類型分布概率時，上文機制滿足以上3個條件。

3.1策略防偽

定理1：式(1)～(3)表示的激勵機制滿足策略性防偽或最優(yōu)策略激勵兼容性，確保每個認證參與者如實地報告自己的能量消耗，即“說真話”是最優(yōu)策略。

3.2個體理性

定理2：對于每一個參與者，式(1)～(3)表示的激勵機制是個體理性的。

證明：個體理性，即機制中網絡節(jié)點若能成功參與外來節(jié)點的接入認證，則一定能得到相應的付酬，且收益函數非負；如果沒有參與，則相應的付酬為零，能量消耗亦為零。

分兩種情況討論：

3.3預算平衡

定理3：式(1)～(3)表示的激勵機制是預算平衡的。

4 激勵機制的納什均衡求解

從認證的過程來看，新節(jié)點廣播認證請求[14]，網內節(jié)點收到請求，并根據自己的信譽度及真實能量給出自己的能量消耗報告予以響應，只有能量報告最少的一個響應節(jié)點i取得認證資格，隨后完成新節(jié)點的認證。從參與認證的節(jié)點i的角度來看，它取得付酬，增加自己的信譽度；從網絡整體來看，擴展了網絡，網中的節(jié)點成員增多帶來路由選擇的多樣化，全體網絡成員共同受益。下面通過分析認證參與節(jié)點的能量消耗報告，繪制參與方的反應曲線，從而確定參與方能量報告決策的納什均衡。

為討論方便，假設無線自組網中只有2個現存節(jié)點，它們參與認證的能量消耗分別為c1與c2，剩余能量分別為ω1與ω2，則留給自己的私人消耗為x1=ω1-c1與x2=ω2-c2。根據“包含型”服務認證分析，無線自組網吸收新節(jié)點后的公共收益為C=max{c1,c2}。在擬線性效用函數的前提下每一個參與者的收益為Scorei(ci)=Ui(C)+xi，i={1,2}，每個節(jié)點的決策問題可表示為

則Scorei(ci)=Ui(C)+xi=Ui(max{c1,c2})+ωi-ci。

(4)

(5)

(6)

同理，節(jié)點2的能量報告策略為

(7)

分3種情況分析納什均衡求解。

圖1 1>2>2>1時節(jié)點的反應曲線Fig.1 Reaction curve when 1>2>2>1

圖2 1>2>2>1時節(jié)點的反應曲線Fig.2 Reaction curve when 1>2>2>1

圖3 1>2>1>2時節(jié)點的反應曲線Fig.3 Reaction curve when 1>2>1>2

上述分析表明，3種情形下文中的激勵機制總能在兼容個體節(jié)點與網絡中所有節(jié)點利益的情況下，選舉出能量保持最優(yōu)的節(jié)點作為入網認證節(jié)點。在組隊參加搶答競賽中存在類似的情境，為了獲得搶答最高分，最好的辦法是小組內成員都積極暴露自己的實力，然后選擇一個尖子成員獨立積極參加搶答，其他成員打打下手就可以。

5 結束語

基于公共物品供給博弈與VCG機制的無線自組網入網認證付酬激勵模型，對促使無線自組網中現存節(jié)點積極參與新節(jié)點認證具有較大的作用。實例中納什均衡分析得出的解也與實踐經驗相符，即當個體理性與集體理性兼容時，為了使個體利益達到最大，節(jié)點從自身收益出發(fā)選擇積極響應入網節(jié)點認證請求，而后從所有響應節(jié)點中選擇能量最優(yōu)的節(jié)點作為認證節(jié)點。然而，在實際應用中不乏出現一些不響應認證請求或不履行認證付酬的“惡意”節(jié)點。下一步還需要就惡意節(jié)點淘汰后無線自組網的抗毀頑存性進行深入研究。

[1] 黃后彪，羅長遠，宋玉龍. 航空自組網漫游接入認證方案[J].計算機應用研究，2013，30(2)：500-502.

HUANG Houbiao，LUO Changyuan，SONG Yulong. Authentication scheme for roaming in aeronautical ad hoc networks[J]. Application Research of Computers, 2013，30(2)：500-502. (in Chinese)

[2] 祝世雄，羅長遠，安紅章，等.無線通信網絡安全技術[M].北京：國防工業(yè)出版社，2014:170-190.

[3] 郭晶晶，馬建峰，李琦，等. 基于博弈論的移動自組織網絡的信任管理方法[J].通信學報，2014,35(11)：50-58.

GUO Jingjing, MA Jianfeng, LI Qi, et al. Game theory based trust management method for mobile ad hoc networks[J]. Journal on Communications, 2014,35(11)：50-58. (in Chinese)

[4] 聞英友，趙博，趙宏. 基于博弈理論的移動自組網激勵機制研究[J].通信學報，2014，35(4)：49-52.

WEN Yingyou, ZHAO Bo, ZHAO Hong. Study on game-based incentive mechanism of mobile ad hoc network[J]. Journal on Communications,2014，35(4)：49-52.(in Chinese)

[5] 劉志新，申妍燕，關新平.一種基于VCG 拍賣的分布式網絡資源分配機制[J].電子學報，2010，38(8)：1929-1932.

LIU Zhixin, SHEN Yanyan, GUAN Xinping. A VCG auction based distributed mechanism for network resource allocation[J]. Acta Electronica Sinica, 2010，38(8)：1929-1932. (in Chinese)

[6] 黃河.網上采購組合拍賣研究[D].北京：清華大學，2006.

HUANG He. Study on online procurement combinatorial auctions[D]. Beijing: Tsinghua University, 2006.(in Chinese)

[7] 劉巖，張國印，何金洲，等. 基于貝葉斯博弈的MP2P高性能安全資源節(jié)點選擇策略[J].通信學報，2016,37(1)：100-105.

LIU Yan, ZHANG Guoyin, HE Jinzhou, et al. MP2P high capacity and security resource node selection strategy based on Bayesian game[J]. Journal on Communications, 2016,37(1)：100-105. (in Chinese)

[8] 許力，陳志德，黃川.博弈理論在無線網絡中的應用[M].北京：科學出版社，2012：85.

[9] 高麗，趙海峰，穆曉敏. 改進的基于合作博弈的資源分配和接入控制策略[J].電訊技術，2012，52(7)：1183-1188.

GAO Li , ZHAO Haifeng, MU Xiaomin. Improved resource allocation based on cooperative game and access control policy[J].Telecommunication Engineering, 2012，52(7)：1183-1188. (in Chinese)

[10] 范思遐，周奇才，熊肖磊，等. 一種動態(tài)博弈的多agent合作機制模型[J].東北大學學報(自然科學版)，2015,36(1)：114-118.

FAN Sixia，ZHOU Qicai，XIONG Xiaolei，et al. Multi-agent cooperation mechanism model based on dynamic game[J].Journal of Northeastern University(Natural Science),2015,36(1)：114-118. (in Chinese)

[11] TADELIS S.博弈論導論[M]. 李井奎,譯.北京：中國人民大學出版社:2015：282-291.

[12] FUDENBERG D, TIROLE J.博弈論[M]. 黃濤，郭凱，龔鵬,等譯.北京：中國人民大學出版社，2010：220-226.

[13] 丁丁，羅四維，艾麗華. 基于雙向拍賣的適應性云計算資源分配機制[J].通信學報，2012,33(Z1)：136-138.

DING Ding, LUO Siwei, AI Lihua. Adaptive double auction mechanism for cloud resource allocation[J].Journal on Communications, 2012,33(Z1)：136-138. (in Chinese)

[14] 王辛果.一種高效的無線自組網全網可靠廣播協(xié)議[J].電訊技術，2015，55 (7)：769-772．

WANG Xinguo．An efficient network wide reliable broadcast protocol for wireless Ad Hoc networks[J]．Telecommunication Engineering，2015，55(7)：769-772．(in Chinese)

GameTheoryBasedDynamicAccessIncentiveMechanismofWirelessAdHocNetworks

WANG Hong1,2,LI Jianhua1,CUI Qiong1
(1.Information and Navigation College，Air Force Engineering University,Xi′an 710077,China;2.Information and Communication College,National University of Defense Technology,Xi′an 710106,China)

The nodes′ limited energy in wireless ad hoc network makes the nodes in the network not respond a recruit node′s access request vigorously. In order to motivate nodes to participate in the authentication,the Vickrey-Clarke-Groves(VCG) mechanism is combined with the public-goods supplying theory,and the access incentive mechanism for wireless ad hoc network is proposed. Furthermore,how to find the authentication’s node is given and how much income/pay the authentication node gets/needs is presented with the study of energy consumption. It is proved theoretically that the mechanism possesses strategy-proof,individual rational and budget-balanced. Meanwhile,game between individual and collectivity is analyzed according to different parameter configuration in the example of this paper,which verifies that the equilibrium can effectively motivate all nodes′ cooperation,and all nodes should participate in a recruit node′s authentication vigorously for its own profit.

wireless ad hoc network;access authentication;game theory;incentive mechanism

date:2016-12-30；Revised date：2017-06-20

國家自然科學基金資助項目(61401499, 61174162)

**通信作者：whongger2006@sina.com Corresponding author：whongger2006@sina.com

TN918；O225

A

1001-893X(2017)10-1177-07

王宏(1979—)，男，陜西澄城人，博士研究生，講師，主要研究方向為無線自組網的信任管理；

Email：whongger2006@sina.com

李建華(1965—)，男，陜西白水人，博士，教授、博士生導師，主要研究方向為空天信息網絡作戰(zhàn)運用；

崔瓊(1990—)，女，河南林州人，博士研究生，主要研究方向為信息系統(tǒng)網絡復雜性分析技術。

10.3969/j.issn.1001-893x.2017.10.013

王宏，李建華，崔瓊.基于博弈論的無線自組網動態(tài)接入激勵機制[J].電訊技術，2017,57(10):1177-1183.[WANG Hong,LI Jianhua,CUI Qiong.Game theory based dynamic access incentive mechanism of wireless ad hoc networks[J].Telecommunication Engineering,2017,57(10):1177-1183.]

2016-12-30；

2017-06-20