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

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

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

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

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

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

無線自組網(wǎng)；接入認(rèn)證；博弈論；激勵機制

1 引 言

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

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

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

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

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

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

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

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

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

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

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

VCG:{A,C,R}。

文中符合及其表達(dá)意義見表1。

表1 文中符號表達(dá)意義Tab.1 Letters and symbols

2.1節(jié)點選舉辦法

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

(1)

2.2新節(jié)點付酬

為了激勵網(wǎng)內(nèi)節(jié)點參與認(rèn)證，機制為參與認(rèn)證的節(jié)點提供付酬，參與節(jié)點i的付酬函數(shù)定義為

(2)

2.3認(rèn)證節(jié)點收益

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

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

(3)

2.4認(rèn)證能量消耗

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

(4)

3 激勵機制的性能分析

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

3.1策略防偽

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

3.2個體理性

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

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

分兩種情況討論：

3.3預(yù)算平衡

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

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

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

為討論方便，假設(shè)無線自組網(wǎng)中只有2個現(xiàn)存節(jié)點，它們參與認(rèn)證的能量消耗分別為c1與c2，剩余能量分別為ω1與ω2，則留給自己的私人消耗為x1=ω1-c1與x2=ω2-c2。根據(jù)“包含型”服務(wù)認(rèn)證分析，無線自組網(wǎng)吸收新節(jié)點后的公共收益為C=max{c1,c2}。在擬線性效用函數(shù)的前提下每一個參與者的收益為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é)點的反應(yīng)曲線Fig.1 Reaction curve when 1>2>2>1

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

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

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

5 結(jié)束語

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

[1] 黃后彪，羅長遠(yuǎn)，宋玉龍. 航空自組網(wǎng)漫游接入認(rèn)證方案[J].計算機應(yīng)用研究，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] 祝世雄，羅長遠(yuǎn)，安紅章，等.無線通信網(wǎng)絡(luò)安全技術(shù)[M].北京：國防工業(yè)出版社，2014:170-190.

[3] 郭晶晶，馬建峰，李琦，等. 基于博弈論的移動自組織網(wǎng)絡(luò)的信任管理方法[J].通信學(xué)報，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] 聞英友，趙博，趙宏. 基于博弈理論的移動自組網(wǎng)激勵機制研究[J].通信學(xué)報，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] 劉志新，申妍燕，關(guān)新平.一種基于VCG 拍賣的分布式網(wǎng)絡(luò)資源分配機制[J].電子學(xué)報，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] 黃河.網(wǎng)上采購組合拍賣研究[D].北京：清華大學(xué)，2006.

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

[7] 劉巖，張國印，何金洲，等. 基于貝葉斯博弈的MP2P高性能安全資源節(jié)點選擇策略[J].通信學(xué)報，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] 許力，陳志德，黃川.博弈理論在無線網(wǎng)絡(luò)中的應(yīng)用[M].北京：科學(xué)出版社，2012：85.

[9] 高麗，趙海峰，穆曉敏. 改進(jìn)的基于合作博弈的資源分配和接入控制策略[J].電訊技術(shù)，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].東北大學(xué)學(xué)報(自然科學(xué)版)，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.博弈論導(dǎo)論[M]. 李井奎,譯.北京：中國人民大學(xué)出版社:2015：282-291.

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

[13] 丁丁，羅四維，艾麗華. 基于雙向拍賣的適應(yīng)性云計算資源分配機制[J].通信學(xué)報，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] 王辛果.一種高效的無線自組網(wǎng)全網(wǎng)可靠廣播協(xié)議[J].電訊技術(shù)，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

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

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

TN918；O225

A

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

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

Email：whongger2006@sina.com

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

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

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

王宏，李建華，崔瓊.基于博弈論的無線自組網(wǎng)動態(tài)接入激勵機制[J].電訊技術(shù)，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