一種基于博弈理論的無線傳感器網(wǎng)絡(luò)自私節(jié)點(diǎn)懲罰機(jī)制

王艷華　孫成啟　高洋等

摘要 針對無線傳感器網(wǎng)絡(luò)中的搭便車現(xiàn)象，基于博弈理論建立自私節(jié)點(diǎn)懲罰機(jī)制。將傳感器的可信度分為多個等級，對其進(jìn)行多策略博弈，使其更加符合無線傳感器網(wǎng)絡(luò)的復(fù)雜性特點(diǎn)，從而激勵節(jié)點(diǎn)對可信合作策略的選取。結(jié)果表明，基于博弈理論的無線傳感器網(wǎng)絡(luò)中自私節(jié)點(diǎn)懲罰機(jī)制可以有效地解決網(wǎng)絡(luò)中的搭便車問題，從而驗(yàn)證了該懲罰機(jī)制的有效性。

關(guān)鍵詞 無線傳感器網(wǎng)絡(luò)；搭便車；博弈；懲罰機(jī)制

中圖分類號 S126 文獻(xiàn)標(biāo)識碼

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由大量的傳感器節(jié)點(diǎn)構(gòu)成的，其構(gòu)成的方式多為自組織形式和多跳形式，這些傳感器節(jié)點(diǎn)可以協(xié)作地感知和處理被感知對象的相關(guān)信息，并且將所感知的信息發(fā)送給網(wǎng)絡(luò)的所有者[1-2]。WSN具有典型的復(fù)雜網(wǎng)絡(luò)特點(diǎn)，其應(yīng)用也變得日趨復(fù)雜，因此，WSN的安全性成為一個亟待解決的問題。傳統(tǒng)的解決WSN的方法主要為基于密碼學(xué)的安全機(jī)制，該方法主要用來抵抗外部攻擊，然而基于密碼學(xué)的安全機(jī)制不能很好地抑制WSN內(nèi)部傳感器節(jié)點(diǎn)的自私行為。

隨著WSN研究領(lǐng)域的逐漸成熟，其信任管理的研究也成為WSN領(lǐng)域的研究熱點(diǎn)。在WSN中，由于資源的有限性，傳感器節(jié)點(diǎn)為了獲取更多的資源而產(chǎn)生節(jié)點(diǎn)的自私行為，從而產(chǎn)生了WSN中的節(jié)點(diǎn)搭便車（Freeriding）問題。然而節(jié)點(diǎn)的這種自私行為嚴(yán)重影響了WSN的網(wǎng)絡(luò)性能以及正常運(yùn)行。

因此，筆者針對無線傳感器網(wǎng)絡(luò)中的搭便車現(xiàn)象，基于博弈理論建立自私節(jié)點(diǎn)懲罰機(jī)制，將傳感器的可信度分為多個等級，對其進(jìn)行多策略博弈，使其更加符合無線傳感器網(wǎng)絡(luò)的復(fù)雜性特點(diǎn)，從而制定更加有效的激勵懲罰機(jī)制，激勵節(jié)點(diǎn)對可信合作策略的選取。

1 激勵懲罰機(jī)制概述

為了解決WSN中的搭便車問題，需要引入信任管理來對傳感器節(jié)點(diǎn)的行為進(jìn)行度量與管理，從而制定相應(yīng)的激勵懲罰機(jī)制來抑制傳感器節(jié)點(diǎn)自私行為的產(chǎn)生。

調(diào)查顯示，在WSN、社會網(wǎng)絡(luò)以及P2P網(wǎng)絡(luò)中，幾乎70%的節(jié)點(diǎn)在交互過程中不分享任何的網(wǎng)絡(luò)資源，并且這些自私節(jié)點(diǎn)對分享信息的用戶進(jìn)行搭便車。在網(wǎng)絡(luò)中，有很少的節(jié)點(diǎn)愿意分享信息或?yàn)槠渌?jié)點(diǎn)提供服務(wù)。幾乎50%的文件查找響應(yīng)是來自信息分享節(jié)點(diǎn)頂部的1%的文件。目前，有關(guān)激勵懲罰機(jī)制的研究已日趨成熟。激勵機(jī)制算法的基本流程如圖1所示。

圖1 激勵機(jī)制算法基本流程

目前，將已提出的激勵懲罰機(jī)制分為基于節(jié)點(diǎn)行為的激勵方法[3-4]、基于博弈論的方法[5-6]以及采用社會網(wǎng)絡(luò)或經(jīng)濟(jì)模型的控制策略[5，7-9]3大類。

1.1 基于節(jié)點(diǎn)行為的激勵方法 最早有關(guān)Freeriding問題的抑制方法是基于節(jié)點(diǎn)行為的激勵方法，該方法得到了廣泛的應(yīng)用。有關(guān)基于節(jié)點(diǎn)行為的激勵方法中的一些相關(guān)問題，如如何計(jì)算節(jié)點(diǎn)信譽(yù)度等，已經(jīng)成為WSN等網(wǎng)絡(luò)的研究熱點(diǎn)。有關(guān)效用函數(shù)的定義、度量以及選擇等問題，是不同的基于節(jié)點(diǎn)行為激勵方法之間的差異[10]。該方法可以有效地防止自私節(jié)點(diǎn)的欺騙行為，并激勵節(jié)點(diǎn)遵守網(wǎng)絡(luò)中的相關(guān)協(xié)議。

然而，在實(shí)際應(yīng)用中，由于分布式的測量和監(jiān)視機(jī)制，節(jié)點(diǎn)之間相互監(jiān)視而產(chǎn)生大量的開銷；并且網(wǎng)絡(luò)的高密度，使產(chǎn)生節(jié)點(diǎn)由于監(jiān)視鄰接節(jié)點(diǎn)而增加其負(fù)擔(dān)等問題。

1.2 基于博弈論的方法 由于WSN的復(fù)雜性，因此可以將節(jié)點(diǎn)的行為建模為長期的博弈過程。節(jié)點(diǎn)有多個策略進(jìn)行選擇，如為系統(tǒng)做貢獻(xiàn)，只接收信息不發(fā)送信息以及貢獻(xiàn)收益平衡等，從而使得自身獲得最大的收益?；诓┺恼摰姆椒ㄊ菍?jié)點(diǎn)策略的選擇進(jìn)行分析，對網(wǎng)絡(luò)中節(jié)點(diǎn)的不同策略進(jìn)行博弈，從而分析出它們之間的關(guān)系[11]。

然而在實(shí)際的WSN、社會網(wǎng)絡(luò)以及P2P等復(fù)雜網(wǎng)絡(luò)的激勵機(jī)制研究中，基于博弈論的方法存在以下兩大主要問題：①目前的基于博弈論的激勵機(jī)制，大多針對的是兩策略進(jìn)行博弈，即完全合作和完全不合作，然而在真實(shí)的復(fù)雜網(wǎng)絡(luò)中，網(wǎng)絡(luò)中節(jié)點(diǎn)的策略存在復(fù)雜性，因此兩策略博弈不能滿足真實(shí)網(wǎng)絡(luò)中策略的復(fù)雜性特點(diǎn)；②現(xiàn)有的基于博弈論的激勵機(jī)制中，所提出的假設(shè)太嚴(yán)格，與真實(shí)的復(fù)雜網(wǎng)絡(luò)環(huán)境存在較大的差異，因此，所得到的納什均衡的準(zhǔn)確性較低。

1.3 基于社會網(wǎng)絡(luò)或經(jīng)濟(jì)模型的控制策略 在WSN、社會網(wǎng)絡(luò)以及P2P網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)的自私行為是用戶個人心理因素的一種延伸，因此可以采用社會網(wǎng)絡(luò)或者經(jīng)濟(jì)模型來研究個人在社會行為中的自私行為。

然而采用社會網(wǎng)絡(luò)或經(jīng)濟(jì)模型的控制策略大多需要有一個集中式的第三方來對節(jié)點(diǎn)的可信行為進(jìn)行審計(jì)。因此，該方法的可擴(kuò)展性較差，從而制約了WSN、社會網(wǎng)絡(luò)以及P2P網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)的發(fā)展，并且在可信度的計(jì)算方面很難得到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的認(rèn)同。因此，由于復(fù)雜網(wǎng)絡(luò)的動態(tài)性和復(fù)雜性特點(diǎn)，這種需要第三方來審計(jì)的方法難以實(shí)現(xiàn)。

針對以上激勵懲罰機(jī)制的不足，基于WSN的特點(diǎn)，該研究基于博弈理論研究WSN的自私節(jié)點(diǎn)懲罰機(jī)制，將傳感器的可信度分為多個等級，對其進(jìn)行多策略博弈，使其更加符合WSN的復(fù)雜性特點(diǎn)，從而制定更加有效的激勵懲罰機(jī)制，激勵節(jié)點(diǎn)對可信合作策略的選取。

2 基于博弈理論的懲罰機(jī)制

傳統(tǒng)的基于博弈理論的激勵懲罰機(jī)制大多針對的是兩策略博弈理論，即將節(jié)點(diǎn)的行為分為兩類策略：自私策略和可信合作策略。則對稱博弈收益矩陣如表1所示，且滿足D>T>S>C，2T>C+D。也就是說，博弈雙方都選擇可信合作策略能夠獲得總體的最高收益。那么，不論對手采取哪種策略，選擇自私策略都是最佳選擇，也就是理性的個體最終會選擇自私的策略。這種自私的狀態(tài)就是系統(tǒng)的納什均衡狀態(tài)。

在WSN中，當(dāng)自私節(jié)點(diǎn)與可信合作節(jié)點(diǎn)進(jìn)行博弈時，自私節(jié)點(diǎn)通過損害可信合作節(jié)點(diǎn)的利益而使自己獲得利益，其行為違背了公平規(guī)范。因此，為了抑制WSN中傳感器自私節(jié)點(diǎn)的產(chǎn)生，該研究提出基于博弈理論的自私節(jié)點(diǎn)懲罰機(jī)制，從而提高可信合作策略的節(jié)點(diǎn)收益，降低自私節(jié)點(diǎn)的收益，激勵節(jié)點(diǎn)對可信合作策略的選擇。則自私節(jié)點(diǎn)的懲罰機(jī)制滿足下面3個特點(diǎn)：

①鼓勵傳感器節(jié)點(diǎn)分享信息和提供服務(wù)；

②為傳感器節(jié)點(diǎn)提供公平的差異化服務(wù)；

③最大化WSN的總體收益。

因此，如果博弈個體受到公平規(guī)范的影響，那么自私節(jié)點(diǎn)的效用收益就會因?yàn)槠茐墓皆斐傻摹皟?nèi)疚”而降低，而可信合作節(jié)點(diǎn)的效用收益則會因?yàn)榉切湃蝹€體違反公平造成額外的“不滿”而增加。

針對該懲罰機(jī)制的特點(diǎn)，基于表1中兩策略博弈的收益矩陣中的各個策略的收益值，該研究給出加入懲罰機(jī)制后的收益計(jì)算方法，如式（1）所示。其中，T*、C*、D*以及S

由于WSN具有復(fù)雜網(wǎng)絡(luò)特性，因此需要將傳感器的行為分為多個等級，需要在兩策略博弈的基礎(chǔ)上進(jìn)行多策略博弈。該研究將傳感器節(jié)點(diǎn)的行為分為4個等級，假設(shè)當(dāng)兩個節(jié)點(diǎn)進(jìn)行博弈時，兩個傳感器節(jié)點(diǎn)的行為等級分別為i和j，且i，j∈（1，2，3，4）相應(yīng)的收益分別為xi和xj，則加入懲罰機(jī)制的多策略收益值計(jì)算方法如式（2）所示，假設(shè)i

3 模擬試驗(yàn)與結(jié)果分析

該研究通過模擬試驗(yàn)來驗(yàn)證該信息傳播模型的有效性。硬件試驗(yàn)環(huán)境為Intel Core（TM） i5-3230M CPU @2.60GHz，12.0 GB內(nèi)存，采用Windows 8操作系統(tǒng)，用Matlab 7.0編程平臺。

該研究模擬WSN中的1 000個不同策略的傳感器節(jié)點(diǎn)數(shù)量變化的演化趨勢，來驗(yàn)證所提懲罰機(jī)制的有效性。圖2所示為沒有加入懲罰機(jī)制的多策略博弈演化結(jié)果。從圖2可以看出，在沒有加入懲罰機(jī)制時，自私節(jié)點(diǎn)主導(dǎo)了整個網(wǎng)絡(luò)的演化方向，也就是產(chǎn)生了搭便車現(xiàn)象。

加入該研究提出的懲罰機(jī)制后，模擬試驗(yàn)結(jié)果如圖3所示。從圖3可以看出，加入基于博弈理論的無線傳感器網(wǎng)絡(luò)中自私節(jié)點(diǎn)的懲罰機(jī)制后，選擇可信合作策略的傳感器節(jié)點(diǎn)最終主導(dǎo)整個WSN的演化方向；并且選擇自私策略的傳感器節(jié)點(diǎn)在網(wǎng)絡(luò)中將最終消失。由此可見，該研究提出的懲罰機(jī)制可以有效地解決WSN中的搭便車問題，從而驗(yàn)證了該懲罰機(jī)制的有效性。

4 結(jié)語

該研究針對WSN中的搭便車現(xiàn)象，基于博弈理論建立自私節(jié)點(diǎn)懲罰機(jī)制，將傳感器的可信度分為多個等級，對其進(jìn)行多策略博弈，使其更加符合無線傳感器網(wǎng)絡(luò)的復(fù)雜性特點(diǎn)，從而制定更加有效的激勵懲罰機(jī)制，激勵節(jié)點(diǎn)對可信合

作策略的選取。試驗(yàn)結(jié)果表明，基于博弈理論的WSN中自

私節(jié)點(diǎn)懲罰機(jī)制可以有效地解決網(wǎng)絡(luò)中的搭便車問題，從而

驗(yàn)證了該懲罰機(jī)制的有效性。

在未來的工作中，將進(jìn)一步研究WSN的復(fù)雜特征，建立更加有效的激勵懲罰機(jī)制來激勵節(jié)點(diǎn)對可信合作策略的選擇，從而提高WSN的整體性能。

參考文獻(xiàn)

[1]

YICK J，MUKHERJEE B，GHOSAL D.Wireless sensor networks survey[J].Computer Networks，2008，52：2292-2330.

[2] HAN G J，JIANG J F，SHU L，et al.Management and applications of trust in Wireless Sensor Networks：A survey[J].Journal of Computer and System Sciences，2014，80（3）：602-617.

[3] ZGHAIBEH M，ANAGNOSTAKIS K G.On The impact of P2P incentive mechanisms on user behavior[R].NetEcon + IBC，2007：1-6.

[4] 謝曉蘭，劉亮，趙鵬.面向云計(jì)算基于雙層激勵和欺騙檢查的信任模型[J].電子與信息學(xué)報.2012，34（4）：812-817.

[5] MA R T B，LEE S C M，LUI J C S，et al.Incentive and service differentiation in P2P Networks：A game theoretic approach [J].IEEE/ACM Tranon Networking.2006：978-991.

[6] 張煜，林莉，懷進(jìn)鵬，等.網(wǎng)格環(huán)境中信任-激勵相容的資源分配機(jī)制[J].軟件學(xué)報，2006，17（11）：2245-2254.

[7]WANG Y，VASSILEVA J.Super-agent based reputation management with a practical reward mechanism in decentralized systems[C]//4th IFIP WG11.11 International Conference on Trust Management.Iwate，Japan，2010：33-40.

[8]WANG Y，ZHANG J，VASSILEVA J.Effective web service selection via communities formed by superagents[C]// Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence.WI，Toronto，Canada，2010：444-451.

[9] GHAFFARINEJAD A，AKBARI M K.An incentive compatible and distributed reputation mechanism based on context similarity for service oriented systems[J].Future Generation Computer Systems，2013，29（3）：863-875.

[10] 胡建理，周斌，吳泉源.P2P網(wǎng)絡(luò)中具有激勵機(jī)制的信任管理研究[J].通信學(xué)報，2011，32（5）：22-32.

[11] 張娓娓，陳綏陽，余洋.基于博弈論的P2P激勵機(jī)制[J].計(jì)算機(jī)工程，2011，37（15）：89-102.