基于博弈論的無(wú)線傳感器網(wǎng)絡(luò)路由算法研究

劉舒拉

摘 要：在通過(guò)博弈論概念建立網(wǎng)絡(luò)模型的基礎(chǔ)上，討論了各種針對(duì)特定傳感器網(wǎng)絡(luò)特點(diǎn)的路由算法。歸納了基于博弈論的無(wú)線傳感器網(wǎng)絡(luò)路由算法的設(shè)計(jì)原則和分類方法。詳細(xì)比較了這些算法的特點(diǎn)、性能差異和應(yīng)用范圍．最后對(duì)無(wú)線傳感器網(wǎng)絡(luò)路由算法的研究現(xiàn)狀進(jìn)行了總結(jié)，并指出未來(lái)的研究重點(diǎn)。

關(guān)鍵詞：博弈論； 無(wú)線傳感器網(wǎng)絡(luò)； 路由算法;網(wǎng)絡(luò)模型

中圖分類號(hào)：TN92-34

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X(2011)09-0045-03

Game-theory Based Routing Algorithms for Wireless Sensor Network

LIU Shu-la

(Department of Electrical Engineering, Xian Aerotechnical College, Xian 710077, China)

Abstract： The various routing algorithms aiming at the characteristics of the specific sensor network are discussed based on the introduction of the game theory concept to establish the network model. The design principle and classification method of routing algorithms for wireless sensor network are summarized. The characteristics, performance difference and application scope of the algorithms are compared in detail. The research status quo of wireless sensor network routing algorithms is described. The research focus of the future research is pointed out.

Keywords： game-theory;wireless sensor network; routing algorithm; network model

0 引 言

由于無(wú)線傳感器網(wǎng)絡(luò)(WSNs)自身的體積、成本、重量和壽命等特點(diǎn)決定了無(wú)線傳感器網(wǎng)絡(luò)最主要的使用方向，再加上自身電源的有限性也限制了它們的計(jì)算以及之間的通信能力，因而需要在網(wǎng)絡(luò)的可靠性和延長(zhǎng)網(wǎng)絡(luò)生存周期之間進(jìn)行均衡。所以，設(shè)計(jì)合理的路由協(xié)議對(duì)降低及平衡網(wǎng)絡(luò)中結(jié)點(diǎn)的能耗，延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間有著重要意義，同時(shí)也是WSNs網(wǎng)絡(luò)協(xié)議研究的重中之重琜1]。

博弈論是一個(gè)相互依存的理論和不確定性條件下的決策。博弈論有三個(gè)組成部分：參與者集合，參與者行為集合，策略集合。當(dāng)博弈執(zhí)行時(shí)，一個(gè)參與者的策略就是一個(gè)完整的行動(dòng)計(jì)劃。參與者可以以自我為中心，以謀取最大利潤(rùn)。因此，一個(gè)參與者的分布式策略，往往可以提供一個(gè)優(yōu)化的解決方案博弈琜2]。

本文研究了基于博弈論路由模型的建立方法。依照博弈論對(duì)結(jié)點(diǎn)問(wèn)題的解決方法，以期幫助與解決無(wú)線傳感器網(wǎng)絡(luò)的問(wèn)題。

1 博弈論模型下的無(wú)線傳感網(wǎng)絡(luò)路由算法

無(wú)線傳感器網(wǎng)絡(luò)中的一個(gè)關(guān)鍵問(wèn)題是路由遙感數(shù)據(jù)的問(wèn)題。無(wú)線傳感器網(wǎng)絡(luò)有效的路由選擇算法包括減少多跳次數(shù)、簇狀構(gòu)造、定向擴(kuò)散和隨機(jī)化算法。然而，在中繼結(jié)點(diǎn)之間有可能會(huì)有合理的干擾，中繼結(jié)點(diǎn)通過(guò)拒絕參加從其他結(jié)點(diǎn)或其他網(wǎng)絡(luò)的結(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包來(lái)保存能量。這樣，就可以通過(guò)提供激勵(lì)來(lái)鼓勵(lì)路由合作，以討論博弈論在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用［3］，如圖1所示。

圖1 博弈論在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用分類

文獻(xiàn)[4]用博弈論分析了一個(gè)博弈的結(jié)果，這些已部署的傳感器屬于不同的簇頭，可以獲得轉(zhuǎn)發(fā)的合作激勵(lì)。當(dāng)傳感器向?qū)儆诓煌仡^的傳感器提出請(qǐng)求服務(wù)時(shí)，其他的傳感器可以根據(jù)自身資源來(lái)選擇支持或拒絕其請(qǐng)求。它完全可能會(huì)自私地拒絕提供支持，以保存自己的資源。在這樣的博弈中，沒(méi)有一方的簇有義務(wù)為其他簇的結(jié)點(diǎn)提供服務(wù)，納什均衡的結(jié)果可確定其是否屬于不同的簇的非合作結(jié)點(diǎn)。為了避免這樣的情況出現(xiàn)，可使用令牌作為激勵(lì)來(lái)鼓勵(lì)屬于不同簇的結(jié)點(diǎn)之間的合作。兩個(gè)簇組織i∈{A,B}部署傳感器{si1,si2,…,sik}可組成2K個(gè)矩形網(wǎng)絡(luò)結(jié)點(diǎn)。令牌的使用可以促進(jìn)每個(gè)簇在時(shí)間周期T內(nèi)完成合作協(xié)議。當(dāng)屬于一個(gè)簇的結(jié)點(diǎn)a請(qǐng)求屬于另一個(gè)簇的結(jié)點(diǎn)b幫助時(shí)，它可發(fā)送一個(gè)綁定令牌的請(qǐng)求。如果請(qǐng)求獲準(zhǔn)，結(jié)點(diǎn)b將接受令牌；否則，結(jié)點(diǎn)a仍然保留該令牌。一個(gè)實(shí)用的傳感器結(jié)點(diǎn)的功能可由請(qǐng)求的數(shù)目由結(jié)點(diǎn)sik提供和接受，通信信號(hào)發(fā)送數(shù)量由sik負(fù)責(zé)，它可以提出請(qǐng)求的總數(shù) ［5］。

一個(gè)可靠的路由，需要廣泛選擇同時(shí)協(xié)作數(shù)據(jù)匯聚工作的傳感器結(jié)點(diǎn)數(shù)量，以增加網(wǎng)絡(luò)信息量和通信資源以及能量消耗的有效合理利用。它們的算法以傳感器為中心，并使用博弈論作為研究方法。在這個(gè)方法中，傳感器作為合理優(yōu)化合作，可以尋找最佳的網(wǎng)絡(luò)架構(gòu)，以實(shí)現(xiàn)傳感器行為的最大化收益。傳感器收益被定義為傳感器行動(dòng)的收益減去獨(dú)自的損耗琜6-7]。

建立相關(guān)的能量存儲(chǔ)路由是收益最大化的關(guān)鍵，一系列的傳感器都是路由活動(dòng)的參與者，當(dāng)匯聚結(jié)點(diǎn)發(fā)送一個(gè)查詢給這一系列傳感器時(shí)，它可被用來(lái)檢測(cè)結(jié)點(diǎn)匹配的遙感屬性。通過(guò)用一個(gè)值vi來(lái)代表匹配程度可以抽象出這樣的算法思想。如果vi=0，則意味該查詢不匹配任何屬性，這確保了高價(jià)值數(shù)據(jù)不惜成本通過(guò)可靠的多路徑路由。發(fā)送結(jié)點(diǎn)通過(guò)選擇最佳系列傳感器可將數(shù)據(jù)傳到接受結(jié)點(diǎn)。每個(gè)傳感器結(jié)點(diǎn)建模作為中繼接受數(shù)據(jù)包時(shí)，只有一個(gè)鄰居結(jié)點(diǎn)，因此，形式上只有一個(gè)鏈路可以連接任意的源結(jié)點(diǎn)和目的結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)策略可以采用二進(jìn)制向量形式{li1,li2,…,lin}，lii=1/0來(lái)代表一個(gè)傳感器結(jié)點(diǎn)si選擇發(fā)送或者不發(fā)送數(shù)據(jù)包給結(jié)點(diǎn)sj。由于每個(gè)接受數(shù)據(jù)的結(jié)點(diǎn)均可作為一個(gè)激勵(lì)到匯聚結(jié)點(diǎn)，故其收益的一個(gè)可靠路徑功能和信息的預(yù)期值也在該結(jié)點(diǎn)，這就決定了其理想的結(jié)果在數(shù)據(jù)匯聚樹(shù)。如果一個(gè)傳感器結(jié)點(diǎn)選擇其他樹(shù)的結(jié)點(diǎn)，則將導(dǎo)致次優(yōu)行為，這會(huì)從其他結(jié)點(diǎn)減小收益。因此，這就形成了博弈的納什均衡的可靠查詢路由。由于網(wǎng)絡(luò)不可靠，傳感器網(wǎng)絡(luò)會(huì)因整個(gè)網(wǎng)絡(luò)目標(biāo)最大化自己的收益?！奥窂饺觞c(diǎn)”的路徑度量會(huì)評(píng)價(jià)各種次優(yōu)路徑。該路徑的弱點(diǎn)決定了有多少結(jié)點(diǎn)獲得偏離當(dāng)前路徑到最優(yōu)路徑。負(fù)偏差表明結(jié)點(diǎn)si更多地從策略和配置路徑受益；正偏差意味著結(jié)點(diǎn)可以有更好的表現(xiàn)。它們也可以展現(xiàn)一組版本稱之RQR，所有路徑結(jié)點(diǎn)分享在路徑上的最差結(jié)點(diǎn)的受益。而不是選擇一個(gè)鄰居結(jié)點(diǎn)，以便在原始博弈中最大化自己的收益。結(jié)點(diǎn)在TRQR模型中可以通過(guò)最大化收益來(lái)妥協(xié)。一個(gè)重要發(fā)現(xiàn)是在假設(shè)結(jié)點(diǎn)成功概率p∈(0,1]，并在結(jié)點(diǎn)i和j之間的路徑損耗cij=c時(shí)，對(duì)于所有的i，j最可靠的路徑就是RQR博弈均衡的路徑。而對(duì)于均衡p，均衡路徑也成為最簡(jiǎn)單路徑(MCP)。在合理的網(wǎng)絡(luò)目標(biāo)情況下，結(jié)點(diǎn)希望自己的收益最大化，而TRQR則較低，因此其繼承了在MRP網(wǎng)絡(luò)中路徑不可靠的缺陷。

2 博弈論的收益

相比于無(wú)線傳感器網(wǎng)絡(luò)中使用經(jīng)典的博弈論來(lái)研究能量效率，在多級(jí)無(wú)線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)包轉(zhuǎn)發(fā)問(wèn)題也可以適用改進(jìn)的博弈論。改進(jìn)的博弈論應(yīng)用可以容許參與者采用預(yù)先設(shè)定好的行為和策略以及只使用本地信息［8］。

假定一個(gè)多級(jí)（異構(gòu)）無(wú)線傳感器網(wǎng)絡(luò)中任意兩個(gè)不相鄰的兩類可以通過(guò)多條路由通信，那么結(jié)點(diǎn)可以自主和通過(guò)它的活動(dòng)鏈接來(lái)優(yōu)化吞吐量并采取優(yōu)化策略。結(jié)點(diǎn)如果多次參與與其他結(jié)點(diǎn)的博弈，那么在重復(fù)博弈中，結(jié)點(diǎn)在給定圈中的行為將受其他結(jié)點(diǎn)的影響。因而，重復(fù)博弈提供了一種方法來(lái)懲罰那些由于沒(méi)有相互合作而減少了在博弈末期的收益的結(jié)點(diǎn)。這可以通過(guò)降低聲譽(yù)和減少獎(jiǎng)勵(lì)來(lái)在博弈末期降低收益。合作的回報(bào)，可以通過(guò)檢驗(yàn)在博弈末期的重復(fù)局?jǐn)?shù)的收益來(lái)實(shí)現(xiàn)。努力提高合作時(shí)間的結(jié)點(diǎn)可以獲得更高的聲譽(yù)，更快的累積獎(jiǎng)勵(lì)將被包含在可靠路由中。每一級(jí)的簇結(jié)點(diǎn)可決定是否轉(zhuǎn)發(fā)數(shù)據(jù)包。博弈結(jié)束時(shí)只有兩類保持活躍，其中一級(jí)類結(jié)點(diǎn)被認(rèn)為是無(wú)效結(jié)點(diǎn)將首先被消耗。

為了發(fā)展合作/叛離矩陣，引入激勵(lì)合作機(jī)制，可在發(fā)送或轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，一類消耗電池能量β和獲取激勵(lì)γ，如果此類拒絕轉(zhuǎn)發(fā)，它們將獲得φ且同時(shí)沒(méi)有成本。事實(shí)上，各類中的所有結(jié)點(diǎn)均可被假定為兩種策略與編譯：合作和缺陷。它們可從非合作參與者獲得值α乘以合作結(jié)點(diǎn)數(shù)量的收益。有兩種情況：在移動(dòng)類之間轉(zhuǎn)發(fā)數(shù)據(jù)包和包轉(zhuǎn)發(fā)在空間分散的固定類。引進(jìn)一個(gè)PG策略的方式如下：合作并繼續(xù)合作直到其他結(jié)點(diǎn)缺陷n(n≥0)次，然后缺陷永久。該策略的收益是整個(gè)期間δ(0<δ<1)加權(quán)后的所有收益總和的加權(quán)。這表明是在靜止類之間的數(shù)據(jù)轉(zhuǎn)發(fā)。如果每個(gè)參與者均執(zhí)行PG策略，則可以實(shí)現(xiàn)納什均衡，此時(shí)的折現(xiàn)因子δ大致趨近于整體。對(duì)于固定類，形成簇后將獲得合作穩(wěn)定收益以及減少背叛剝離。相對(duì)于移動(dòng)類，變異已經(jīng)被證明是基于動(dòng)力學(xué)進(jìn)化的惟一的穩(wěn)定收益。而對(duì)于移動(dòng)類轉(zhuǎn)發(fā)數(shù)據(jù)包，假定隨著參與者合作的數(shù)量增加，合作收益也在增加。然而，在靜止類中的收益穩(wěn)定的戰(zhàn)略合作則需依靠α，高值α甚至對(duì)固定類都是一個(gè)不穩(wěn)定合作琜9]。這些結(jié)果可參見(jiàn)圖2的總結(jié)。

圖2 基于改進(jìn)博弈論的WSNs靜態(tài)和動(dòng)態(tài)博弈的穩(wěn)定收益

3 結(jié) 語(yǔ)

本文討論了通過(guò)博弈論相關(guān)概念來(lái)解決無(wú)線傳感器網(wǎng)絡(luò)（WSNs）中的多種路由算法問(wèn)題?？偨Y(jié)了多種兼顧結(jié)點(diǎn)能量與結(jié)點(diǎn)分布的傳感器網(wǎng)絡(luò)路由算法。其中基于博弈論的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇節(jié)能路由算法［10］是一種比較高效節(jié)能的網(wǎng)絡(luò)分簇算法。而其不足之處在于它隨機(jī)選舉簇首的方式破壞了網(wǎng)絡(luò)的負(fù)載均衡性，而這可能會(huì)導(dǎo)致網(wǎng)絡(luò)壽命的縮短和傳輸吞吐量的降低；基于博弈論的非均勻分簇策略，可以解決結(jié)點(diǎn)能耗分布不均的難題。

參考文獻(xiàn)

［1］TONG W T, CULLER D E. Taming the unde relying challenges of reliable multihop routing in sensor networks[C]//Proceedings of ACM SENSYS. Los Angeles, CA, USA: ACM, 2003: 14-27.

［2］范如國(guó),韓民春.博弈論［M］.武漢:武漢大學(xué)出版社,2007.

［3］MILLER D, TILAK S, FOUNTAIN T. ″Token″ equilibria in sensor networks with multiple sponsors [C]// Proceedings of the Workshop on Stochasticity in Distributed Systems. San Jose, CA: WSDS, 2005: 5-13.

［4］KANNAN R, IYENGAR S S. Game-theoretic models for reliable pathlength and energy-constrained routing with data aggregation in wireless sensor networks [J]. IEEE Journal of Selected Areas in Communications, 2004, 2: 1141-1150.

［5］RAICU I. Local load balancing for globally efficient routing in wireless sensor networks [J]. International Journal of Distributed Sensor Networks, 2005, 1: 163-185.

［6］DAI H, HAN R. A node-centric load balancing algorithm for wireless sensor networks [C]// Proceedings of IEEE Global Communications Conference on Wireless Communications. [S.l.]: IEEE, 2003, 1: 548-552.

［7］CROSBY G V, PISSINOU N. Evolution of cooperation in multi-classwireless sensor networks [C]// Proceedings of the 32nd IEEE Conference on Local Computer Networks. [S.l.]: IEEE, 2007: 489-495.

［8］SADAGOPAN N, SINGH M, KRISHNAMACHARI B. Decentralized utility based sensor network design [J]. Journal of ACM Mobile Networks and Applications, 2006, 3: 341-350.

［9］HARVEY N J, LADNER R E, LOVASZ L, et al. Semi-matchings for bipartite graphs and load balancing [C]// Proceedings of Workshop of Algorithms and Data Structures. [S.l.]: WADS, 2003: 294-306.

［10］楊寧,田輝,黃平,等.基于博弈理論的無(wú)線傳感器網(wǎng)絡(luò)分布式節(jié)能路由算法［J］.電子與信息學(xué)報(bào),2008,30(5):1230-1233.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文