基于博弈論的QoS協作WSNs路由算法

摘 要： 針對無線傳感器網絡中各個節點之間通信路由單一、無法充分調動合適的路由節點用于下一跳協作通信而浪費不必要的帶寬、時延和能耗，提出一種基于博弈論的QoS協作路由算法（QACR），通過研究各個傳感器節點的距離、能耗速度與QoS需求量之間的博弈關系，建立基于QoS需求的博弈模型。將協作通信和路由機制相結合，在博弈模型的理論基礎上為中心節點選擇一個或者多個中繼節點，共同協作將數據包發送至目的地址。仿真驗證結果表明，這種方法可以減少節點通信的能量消耗和網絡延遲，避免網絡由于能耗過快、節點死亡率過高而導致的網絡斷層或癱瘓，保證網絡的可靠性QoS需求。

關鍵詞： 博弈論； QoS； 協作通信； 無線傳感器網絡； 路由協議

中圖分類號： TN915?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2016）16?0108?04

Abstract： In wireless sensor networks， the communication route among nodes is single， can not be fully mobilized， and cause the unnecessary waste of bandwidth， delay and energy consumption. Therefore， a QoS cooperative routing algorithm based on game theory is presented in this paper. A game model based on QoS demand is established by studying the game relationship between energy consumption rate and distance of each sensor node， and demand of QoS. In combination with the cooperative communication and routing mechanism， one or more relay node is selected for the central node on the basis of the game model theory to transmit data packets to the destination address. The simulation results show that this method can reduce the energy consumption and network delay of the node communication， and avoid network fault and paralysis caused by excessive energy consumption， high node mortality caused， so as to improve network reliability.

Keywords： game theory； QoS； cooperative communication； wireless sensor network； routing protocol

0 引 言

在人機交互愈加頻繁的現代科技世界中，人類對事物感知的精確度和實時性需求越來越高，環境監測、交通管理、國防軍事和國家安全以及一些應急通信應用需要優良先進的網絡部署和業務承載方案。無線傳感器網絡（WSNs）能夠實現傳感器節點在監控區域內檢測數據，并能自由地組網通信，具有廣闊的應用前景。由于無線自組織網絡節點能量有限，WSNs現在面臨最重要的問題是如何在不影響其自身通信性能的前提下有效延長網絡的生命周期，保證網絡的QoS需求。

目前有大量學者在對改進WSNs性能方面做出了很大的貢獻。文獻[1]首次提出了著名的LEACH算法，利用分布式方法在傳感器節點群中以一定的概率競爭簇首節點（CHs），極大降低了節點在數據通信中耗費的能量，但無法在全局協同的情況下確定合適的CHs數量，維持CHs與成員節點數量、網絡能量消耗速度以及節點壽命的平衡穩定。博弈論用來研究某些活動參與者的行為在一些主動或被動作用的影響下的決策方式與均衡問題。它已被廣泛的應用在WSNs的優化和配置中，李明欣等人對非合作博弈的無線資源分配中的納什均衡點的存在性和惟一性進行論證[2]，用接入控制算法動態地調整網絡中某一區域分配的連接數量，保證通信的可靠性。鄢旭等人針對WSNs功率分配優化需求[3]，利用非合作博弈原理，將功率分配問題轉換為信干噪比收益，利用節點移動特征在轉發過程中減少消息的復制轉發次數，為節點提供發射功率策略，提高消息遞交率并降低網絡能耗。

本文提出一種基于博弈論的QoS協作路由算法（QACR），針對無線傳感器網絡中各個節點之間通信路由單一、無法充分調動合適的下一跳節點用于協作通信而浪費不必要的帶寬、時延和能量等問題，研究各個傳感器節點的距離、能耗速度、協作傳輸能力與QoS需求量之間的博弈關系，建立基于QoS需求的博弈模型；并將協作通信和路由機制相結合，通過為路由上的節點選擇一個或者多個中繼節點協助發送數據包，以減少節點的能量消耗和網絡延遲，避免網絡由于能耗過快、節點死亡率過高而導致的網絡斷層或癱瘓，保證網絡可靠性和QoS需求。

1 網絡協作通信架構

WSNs節點通常隨機散布于廣闊的監測區域中，采用分簇協作的網絡模型，如圖1所示。

簇內節點將采集到的信息發送到CHs經數據融合后統一發送至基站（Sink），當CHs無法與Sink直接通信時，就必須建立中繼節點連接CHs之間的通信。本文將協作通信與路由機制相結合，通過為路由中的節點選擇一個或者多個中繼節點協助轉發數據包，實現CHs間的協作通信。 采用的WSNs模型具有以下特點：

（1） WSNs中的N個傳感器節點隨機分布在邊長為L的正方形區域中，無線傳感器網絡[G（N，E，W）]中存在節點[ni]及其鄰居節點mi；

（2） 節點ni可以通過某條路由[eij=ni，nj]將自己的數據轉發，總的路由集合為E；

（3） 節點ni與nj之間的距離為dij，最大距離為R，由此得：[?ni，nj∈N，dij≤R?ni，nj∈E]；

（4） CHs負責數據融合和外界通信；Sink節點是固定的、可維護的并且有足夠的能量供應；

（5） 所有節點具有相同的規格和有限的能源供應，都可以充當CHs和成員節點。節點初始能量為[Estart]，并且所有節點的能量閾值都為[Ethres]，在經過每輪的數據傳輸之后節點剩余能量為Eremain。

在數據傳輸之前，每個簇群需確定自己的協作傳輸單元來協調數據的匯聚和發送。作為協作傳輸單元的成員節點（中心節點）在網絡簇群中有大量的鄰居節點（數目為n），當n越大時，該中心節點就具有很強的能力來為內部節點傳送數據，因此中心節點就必須保證自己有足夠的剩余能量，用于維持作為協作傳輸單元的成員節點的能量消耗和生存時間。根據節點的舒適能量和剩余能量得出節點協作傳輸能力的評估公式為：

[C=λn+（1-λ）EstartEremain] （1）

QoS用來衡量網絡路由效用的可靠標準。通過研究網絡鏈路質量中各參數的影響程度，計算出每個節點ni的偏移度參數θi和敏感度因子[φi0<φi≤1]，若網絡的最大參數偏移度為Ti，則網絡的總偏移度系數為：

[Pi=i=1kφiTi-θi] （2）

采用人工神經網絡學習算法中的Sigmoid函數，實現網絡中不同節點的QoS統一量化[4]：

[Qi=A1+exp-BPi] （3）

通過對QoS的統一量化，可以將QoS需求從一個抽象的概念轉化為形象具體的數據量用于之后建立準確的博弈模型。

2 基于博弈論的路由算法

網絡模型中的節點都有自私理性的偏向，每個傳感器節點都想使自身用于數據通信的能量最小化，以達到最長的壽命，對于自身檢測到的或中途轉發的數據都會進行丟棄或者轉發的選擇。本文的路由協作算法在網絡協作通信的過程中對傳輸單元和鄰居協作傳輸單元進行不斷的博弈，最終為節點找到合適的路由，確定各個網絡元素的性質，在滿足網絡QoS需求的前提下盡可能延長網絡的生存時間和QoS需求。

2.1 博弈模型

博弈論用來研究某些活動參與者的行為在一些主動或被動作用的影響下的決策方式，或者某種行為的均衡問題，它以數學為基礎研究行為活動中的參與者如何做出決斷從而獲得最大利益。傳感器節點的能耗、感知傳輸數據總量，以及網絡的生命周期和可靠度等都是衡量WSNs性能的標準。本文研究的主要對象是基于博弈論的思想設計出網絡中節點相互協作的路由算法，目的是使節點在合作路由的過程中能聯合優化網絡性能，保證其QoS效果，盡可能地延長網絡的生命周期。因此設定節點理性偏好為：

（1） 盡可能保證網絡的運行周期和QoS效果[5]，防止節點過早死亡造成網絡癱瘓，發生通信斷層；

（2） 在保證自身能量消耗最低的前提下，將足夠多的感知數據量傳輸到基站。

針對上述WSNs節點的理性偏好，結合節點位置、能耗情況、節點協作傳輸能力以及網絡的協同架構等方面，給出路由博弈模型：

網絡行動順序：當節點被隨機部署在環境中開始感知數據便是一輪網絡博弈的開始，源節點選擇合適的路由將數據傳輸到下一跳節點或者CHs，通過多跳傳輸到基站，每個參與者都根據前面節點的策略，找到收益最高的路由策略，周而復始直至節點自身能量被消耗殆盡而中斷使用。

網絡策略：策略是指博弈成員可選擇的行為集合，當節點接收到網絡中其他節點傳輸的數據包時，可以放棄轉發數據或選擇鄰居節點轉發數據兩種策略，用集合的形式表示為：[Ti={ti1，ti2，…，tii-1，tii，…，tim}]。

網絡效益函數：同所有博弈模型一樣，網絡需要在花費一定代價的前提下才會有效益出現，因此必須權衡最優的路由選擇作為博弈策略，以將數據發送到目的地址為效益體現。

設需轉發數據的CHs對QoS的需求量為[Q=（Q1，Q2，…，Qi，…，Qk）]，不同節點QoS之間的競爭因子為[η，η∈（0，1]]時，備選節點QoS無差異；[η=0]時則說明這個節點的QoS具有極強的路由優勢[6]。計算出節點ni對應QoS需求向量的效率因子為：

[ei=C21-i=1kφiθii=1kφi] （4）

網絡中的成員節點進行通信時能量消耗速度越大，則節點的生命強度就越弱，容易導致整個無線傳感器網絡過早衰竭或癱瘓。而中心節點ni與中繼節點nj之間的距離也是決定網絡節點協作通信性能的重要原則之一，選擇合適的中繼節點可以避免不必要的數據冗余和延遲。本文提出的博弈模型的效用函數基于網絡QoS需求量Qi、節點的能耗速度vi，ni與nj之間的距離dij以及節點協作傳輸能力C，路由選擇博弈模型中的總效用函數為：

[P（Q）=Ci=1KQiEi-i=1KQi22-i=1KQidijvi-ηi≠jQiQj] （5）

當[P（Q）]的值最大時便可得到最佳的QoS需求量，對式（5）中的Qi求導得：

[?PQ?Qi=eiC-Qi+ηi≠jQj-dijvi] （6）

[Qi=eiC+ηi≠jQj-dijvi] （7）

令式（6）為零，當式（7）成立時，路由選擇博弈模型的總效用函數達到最大，此時，WSNs中的節點可以在能量消耗、通信延遲以及數據冗余最小的情況下，成功傳輸數據至目的地址。這樣便可延長網絡的生命周期，滿足網絡QoS需求。路由選擇發生時，中心節點與中繼節點之間就會開始一場選擇與判斷轉發的博弈過程。此時發送協作傳輸的節點與每一個鄰居協作傳輸節點成為博弈的參與者，根據節點的QoS需求量以及博弈效用值判斷路由決策，選擇合適的路由傳送數據。

2.2 路由選擇機制

協作通信可以產生空間分集以抵抗信道衰落，提高信息發送成功率。本文將協作通信和路由機制相結合，通過為路由上的節點選擇一個或者多個中繼節點用于協助發送數據包至目的地址，減少節點的能量消耗和網絡延遲，提高系統可靠性，保證其QoS效用。在前文研究WSNs協作通信模型和博弈效益模型的基礎上，綜合考慮協作節點ni，nj之間距離、網絡QoS需求量以及博弈效用值等信息，提出一種基于博弈論的QoS協作路由算法（QACR），路由選擇機制的設計思路如下：

Step1：建立網絡博弈模型。包括元素主要有：參與者節點集合N、節點ni在每一輪選擇的路由策略集合[Ti]，以及博弈效用值[Pij]；ni廣播自己的效用值消息[P_msg]給鄰居節點，建立鄰居節點信息集合；

Step2：簇內通信的CHs選擇過程。所有的節點產生隨機數c，當節點的隨機數小于T值時，該節點成為候選CHs，自己廣播成為候選CHs的消息Candi_msg給通信范圍內的所有節點；候選CHs比較自己和鄰居節點效用值[Pij]的大小，為保證博弈模型的效用最大，選擇[Pij]值較大的節點作為正式CHs，廣播成為正式CHs的消息；

Step3：選擇合適的下一跳CHs。作為中心節點的CHs，如果必須通過中繼節點間協作才能將數據送到目的地址，就首先需要評估與各個鄰居節點之間的博弈效用值[Pij]，以獲得最大的收益[7]。距離較近且[Pij]值越大的鄰居節點轉發數據的可能性更大，更有可能成為合適的協作傳輸單元；

Step4：簇間通信后的路由轉發過程，接收到數據的協作傳輸節點發送接收消息Recis_msg給中心節點，表示同意搭建路由協作傳輸上一跳的信息；

Step5：通過路由正式發送數據。CHs廣播建簇消息Estab_msg給簇成員節點和協作節點，節點ni接收CHs的確認和時間表，準備發送數據；CHs加入時分多址（TDMA）表，開始接收簇內成員節點發來的感知數據，融合數據并將結果傳送給Sink。

以上步驟之后進入穩定傳輸階段，節點將數據傳輸給CHs，再由CHs發送給下一跳的中繼節點，期間自身的能量慢慢減少直至消耗殆盡，節點死亡。網絡中的節點數量減少，沒有被檢測到數據或者被遺漏的區域越來越多，最后網絡癱瘓，博弈代價體現。

2.3 能耗分析

WSNs中的每個節點都是自私理性的，都想節約自己的能量實現自身效益的最大化。假設消息傳輸中電路發射端消耗的能量為Etrans，Eenlar為前一輪路徑衰減之后的功率放大能量，CHs之間直接通信k b數據所需的能量為：

[Ed=Ed_trans+Ed_enlar=kEcεdij2+k（Ecs+Ecr）] （8）

簇間協作通信時，若源CHs選擇了[（m-1）（m≥1）]個協作節點向目標地址發送數據，將源CHs看作第m個協作節點[8]。采用協作路由的辦法進行數據傳輸時，發送k b的通信量所需的總能量為：

[E=Etrans+Eenlar=kmEcεi=1md2ij+kmEcs+Ecr] （9）式中：[Ec]是在給定誤碼率條件下接收端正確接收1 b數據所需的最低能量；[Ecs，Ecr]分別表示發送電路損耗和接收電路損耗。由式（9）可以得出，只有減少用于數據傳輸的發送和接收電路，即減少數據傳輸量或路由跳轉次數[9]，才能減小網絡能耗，延伸生命周期。

3 仿 真

本文在通過仿真實驗對算法性能進行評估，仿真環境為模擬監控網絡中100個節點隨機分布在200單位的區域中，假設傳輸環境完全并且不受其他干擾因素影響，監測網路能在除自身因素之外可靠運行[10]。MAC層采用IEEE 802.15.4協議，具體網絡參數如表1所示。

表1 網絡參數表

圖2是將文獻[8]中的GARA算法、AODV算法、LEACH算法同QACR算法的平均跳數進行比較，當源節點與目的節點之間的距離一定時，節點都是通過多跳將數據傳輸到目的節點，每個算法的平均跳數都在隨著距離的增加而增加。由圖2可以看出AODV，LEACH算法從一開始節點相距最近的時候跳數較大，QACR算法則一直保持基本穩定的跳數并稍高于GARA算法。在距離最大的時候節點的跳數也達到極值，但QACR算法明顯低于其余三種算法，這是由于WSNs節點之間的協同通信以及通過博弈效用公式得到了非常合適的中繼節點。在多跳數據傳輸時，QACR通過博弈選擇協同中繼節點可以減少節點跳轉次數，降低網絡通信時延。

圖3是網絡能量消耗情況，網絡總能耗隨著通信輪數增大而增大，當輪數到達極限時網絡能量消耗達到頂峰，出現節點死亡或網絡癱瘓等情況。由圖像的斜率可以得出QACR算法的能量消耗速率低于AODV，LEACH和GARA。這是通過博弈模型選擇出合適協作節點可以降低網絡通信跳數，減少不必要的能量消耗和數據冗余，從而延長網絡的生命周期，保證網絡的QoS質量。

4 結 語

本文提出了基于博弈論的QoS協作路由算法，首先分析了傳感器節點的距離、能耗速度與QoS需求量之間的博弈關系，建立基于QoS需求的博弈模型；其次將協作通信和路由機制相結合，在博弈模型的理論基礎上為中心節點選擇一個或者多個中繼節點，共同協作將數據包發送至目的地址。最后仿真驗證，這種方法可以減少節點通信的能量消耗和網絡延遲，避免網絡由于能耗過快、節點死亡率過高而導致的網絡斷層或癱瘓，為網絡可靠性和QoS需求提供很好的保證。

注：本文通訊作者為張天嬌。

參考文獻

[1] HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy?efficient communication protocol for wireless microsensor networks [C]// Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawaii： IEEE， 2000： 1?10.

[2] 李明欣，陳山枝，謝東亮，等.異構無線網絡中基于非合作博弈論的資源分配和接入控制[J].軟件學報，2010，21（8）：2037?2049.

[3] 鄢旭，陳晶，杜瑞穎，等.基于博弈論的無線網絡功率優化模型[J].計算機應用研究，2012，29（4）：1483?1485.

[4] 趙昕，張新.基于博弈論的無線傳感器網絡簇間路由選擇算法[J].計算機應用，2013，33（7）：1813?1815.

[5] SHI T， HAN Z， YANG B. QoS evaluation for several typical topologies and routing algorithms of some WSNs in high?speed railway [C] // Proceedings of 2015 27th Chinese Control and Decision Conference （CCDC）. China： IEEE， 2015： 1402?1407.

[6] 孫慶中，余強，宋偉.基于博弈論能耗均衡的 WSN 非均勻分簇路由協議[J].計算機應用，2014，34（11）：3164?3169.

[7] ALSKAIF T， ZAPATA M G， BELLALTA B. Game theory for energy efficiency in wireless sensor networks： latest trends [J]. Journal of network and computer applications， 2015， 11（54）： 33?61.

[8] 楊云，孔秀平，顏然，等.面向博弈的無線傳感器網絡自適應路由算法[J].小型微型計算機系統，2013，34（10）：2281?2285.

[9] RANI S， MALHOTRA J， TALWAR R. Energy efficient chain based cooperative routing protocol for WSN [J]. Applied soft computing， 2015， 9（35）： 386?397.

[10] RAJA P， DANANJAYAN P. Game theory based cooperative MIMO routing scheme for lifetime enhancement of WSN [J]. International journal of wireless information networks， 2015， 22（2）： 116?125.