基于博弈論的無線傳感器網絡路由算法研究

劉舒拉

摘 要：在通過博弈論概念建立網絡模型的基礎上，討論了各種針對特定傳感器網絡特點的路由算法。歸納了基于博弈論的無線傳感器網絡路由算法的設計原則和分類方法。詳細比較了這些算法的特點、性能差異和應用范圍．最后對無線傳感器網絡路由算法的研究現狀進行了總結，并指出未來的研究重點。

關鍵詞：博弈論； 無線傳感器網絡； 路由算法;網絡模型

中圖分類號：TN92-34

文獻標識碼：A

文章編號：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 引 言

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

博弈論是一個相互依存的理論和不確定性條件下的決策。博弈論有三個組成部分：參與者集合，參與者行為集合，策略集合。當博弈執行時，一個參與者的策略就是一個完整的行動計劃。參與者可以以自我為中心，以謀取最大利潤。因此，一個參與者的分布式策略，往往可以提供一個優化的解決方案博弈琜2]。

本文研究了基于博弈論路由模型的建立方法。依照博弈論對結點問題的解決方法，以期幫助與解決無線傳感器網絡的問題。

1 博弈論模型下的無線傳感網絡路由算法

無線傳感器網絡中的一個關鍵問題是路由遙感數據的問題。無線傳感器網絡有效的路由選擇算法包括減少多跳次數、簇狀構造、定向擴散和隨機化算法。然而，在中繼結點之間有可能會有合理的干擾，中繼結點通過拒絕參加從其他結點或其他網絡的結點轉發數據包來保存能量。這樣，就可以通過提供激勵來鼓勵路由合作，以討論博弈論在無線傳感器網絡中的應用［3］，如圖1所示。

圖1 博弈論在無線傳感器網絡中的應用分類

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

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

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

2 博弈論的收益

相比于無線傳感器網絡中使用經典的博弈論來研究能量效率，在多級無線傳感器網絡中的數據包轉發問題也可以適用改進的博弈論。改進的博弈論應用可以容許參與者采用預先設定好的行為和策略以及只使用本地信息［8］。

假定一個多級（異構）無線傳感器網絡中任意兩個不相鄰的兩類可以通過多條路由通信，那么結點可以自主和通過它的活動鏈接來優化吞吐量并采取優化策略。結點如果多次參與與其他結點的博弈，那么在重復博弈中，結點在給定圈中的行為將受其他結點的影響。因而，重復博弈提供了一種方法來懲罰那些由于沒有相互合作而減少了在博弈末期的收益的結點。這可以通過降低聲譽和減少獎勵來在博弈末期降低收益。合作的回報，可以通過檢驗在博弈末期的重復局數的收益來實現。努力提高合作時間的結點可以獲得更高的聲譽，更快的累積獎勵將被包含在可靠路由中。每一級的簇結點可決定是否轉發數據包。博弈結束時只有兩類保持活躍，其中一級類結點被認為是無效結點將首先被消耗。

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

圖2 基于改進博弈論的WSNs靜態和動態博弈的穩定收益

3 結 語

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

參考文獻

［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］范如國,韓民春.博弈論［M］.武漢:武漢大學出版社,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］楊寧,田輝,黃平,等.基于博弈理論的無線傳感器網絡分布式節能路由算法［J］.電子與信息學報,2008,30(5):1230-1233.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文