基于博弈論的WSN有效分簇路由算法的研究

孫艷琴，熊慶國

（武漢科技大學 信息科學與工程學院，湖北 武漢 430081）

無線傳感器網絡包含了大量無線傳感節點。數字電路、無線通信、電池制造技術和微機電系統技術的進步使無線傳感器節點變得更小、更廉價、功能更強大且更可靠，同時節點的壽命也逐漸延長。由于在許多情況下無線傳感器節點無法從外界獲取能量也無法更換電池，因此，無線傳感器網絡的持續工作能力常依賴于無線傳感節點的電池容量。另外，絕大多數無線傳感器網絡使用多跳通信來避免高能耗、長距離傳輸。每個傳感器節點直接與領域節點通信。因此單個節點能力不足將加重其領域節點的通信負擔，從而使部分區域節點的能量很快消盡，最終使整個無線傳感器網絡失效。

在無線傳感器網絡中，路由協議[1]起著及其重要的作用，而分簇路由協議更是能均衡網絡的能耗，解決無線傳感器網絡能量受限的問題。分簇路由算法是一種兩成架構的傳感器網絡，其邏輯上可以分為簇內層和簇間層，簇頭和其簇內節點構成了簇內層，所有的簇頭和sink節點構成了簇間層。簇內層和簇間層按照其路由跳數亦可分為單跳網絡和多跳網絡。單跳網絡（如LEACH等），其簇內節點到簇頭、簇頭到sink節點均為單跳路由；多跳網絡（如LSCP、PEGASIS、ECMR等），其簇內節點到簇頭、簇頭到sink節點均為多跳路由，則從源節點到目標節點直接可以選擇多條路徑。圖1為分簇多跳網絡。

圖1 分簇多跳網絡Fig.1 Cluster-based multi-hop network

LEACH[2]（Low EnergyAdaptiveClusteringHierarchyProtocol）是第一個基于分簇的路由協議，基本思想是網絡中的節點自組組織成簇，在簇結構中，簇首要收集簇內節點采集的數據，同時還要承擔路由功能，將簇內節點的冗余數據融合處理后再轉發給基站。LEACH隨機循環選擇簇頭結點，將整個網絡的能量負載平均分配到每個結點，從而降低網絡能量消耗，延長網絡生命周期，但是這種隨機產生的方式存在以下的缺陷：

1）不能保證簇頭節點的均勻分布，不能保證簇的規模的合理性，可能出現的情況是：符點密集的地方簇頭節點多，如果產生了多個簇頭節點，會產生冗余，造成能量的不合理消耗，從而影響網絡壽命；節點稀疏的地方簇頭節點少或者沒有產生簇頭節點，那么部分節點可能沒有簇頭節點，將造成網絡的不完全連通。

2）在LEACH算法中，節點根據自身通信代價最小原則選擇加入哪個簇，但是這種方式不能保證簇的負載平衡，因為沒有考慮到遠離基站較遠的簇頭能量耗費過快的問題。

針對LEACH算法存在的不足，本文提出一種基于博弈論的有效分簇路由算法 （game efficient clustering routing：GECR）。為了解決路由算法中整體與個體的矛盾，本文在此基礎上引入經濟學中分析沖突與合作的博弈理論[3]，在簇準備階段，引入簇首的支付函數A，每一個節點根據支付函數A得出的最佳簇首選擇方案，即最佳策略集合；在就緒階段，簇首根據MTE多跳路由協議[4]與基站通信，避免遠離基站的傳感器節點能耗過大，從而實現WSN整體能耗均衡。

1 基于博弈論的有效分簇路由算法

1.1 網絡模型的構建

無線傳感器網絡模型[5]基于以下假設：

1）N個傳感器節點隨機分布在一個m×m的正方形區域內，節點總有數據傳送到基站，基站遠離監測區域并用于接入到有線網絡或者蜂窩無線網絡。

2）每個節點具有唯一ID，為了避免網絡拓撲結構頻繁改變，假定節點部署后不再移動，基站惟一且位置固定。

3）每個節點都具有相同的處理和通信能力，在網絡中的地位平等。

4）每個節點都具備數據融合處理功能，節點之間連接對稱。

5）每個節點可以根據它與接收者的距離遠近，自由調整發射功率以節省能量。

6）網絡節點組織成簇結構的形式，簇首執行數據融合處理以減少簇內節點產生的冗余數據，并負責將集中后的數據傳輸到基站。

1.2 建立節點支付方程

文中綜合考慮了節點剩余能量以及鄰節點到節點自身的平均路徑損耗，將節點i成為簇首的支付函數為

在支付方程中，Ei為節點i的剩余能量，ni為在節點i范圍內的鄰節點數目，∑Ppathloss表示鄰節點到節點i的路徑損耗之和，而Einil與PGen分別是節點的初始能量以及節點間傳輸時的最大傳輸路徑損耗。因此，Ei/Einil表示節點的歸一化能量，保證了節點在剩余能量較少的情況下，成為簇首的概率較小；而∑Ppathloss/ni·PGen表示節點周圍鄰節點到自身的平均路徑損耗歸一化，該值保證鄰節點到備選簇首的平均路徑損耗較小的節點，成為最終簇首的概率較大，調節參數a為方程調節因子。

1.3 決策過程

1）利用博弈思想建立網絡模型，包括：參與人集合S{s1，s2，…sn}；所有節點在某個時刻的策略所構成的策略集L{l1，l2，…ln}；以及節點i成為簇首時的支付函數A；

2）每一個節點建立鄰節點信息集合，并廣播A值；

3）接收到鄰節點A值的節點，將其與自身A值進行比較，并將大于自身A值的鄰節點記錄到鄰節點信息集中；

4）如果節點的鄰節點信息集為空，則自動成為簇首，并廣播簇首選擇信息；接收到一個或多個簇首選擇信息的鄰節點，發送歸屬信息加入A值最大的簇首節點，此時若多個簇首選擇信息中的簇首節點具有相同的A值，則隨機選擇一個作為歸屬簇并發送歸屬信息；

5）如果無線傳感器節點收到了來自自身鄰節點信息集中某個節點發送的歸屬信息，卻沒收到任何簇首選擇信息，則表明該節點不在任何已生成簇首的傳輸范圍之內，該節點將由鄰節點信息集中刪去已有歸屬簇的鄰節點，并回到4）；

6）當所有參與人均決定自身策略后，并開始數據傳輸。

由以上步驟可以看出，在整個過程中，博弈分階段進行，所有參與人在某一階段選擇策略行動時均知道所有相關參與人在以前階段所選擇的行動；其次所有參與者在選擇行動時均是根據所有相關參與人的歷史行動策略以及相關信息做出策略選擇；再次該多階段博弈的策略組合在每一個階段均為納什均衡；而最終策略組合為完美子博弈均衡。

2 仿真分析

2.1 參數設置

用Matlab[6]生成一個節點分布圖，將100個節點隨機分布在一個介于（X=0，Y=0）與（X=100，Y=100）的區域內。 sink點置于（50，50）處，其能量可連續供給，如圖2所示。在仿真軟件中進行參數設置后，分別對網絡平均耗能和存活節點的數量進行仿真，結果如圖3和圖4所示。實驗表明，基于博弈論的有效分簇路由算法不但能推遲了節點的死亡時間，而且網絡總體平均耗能也相應的減少，無線傳感器網絡的壽命得到了有效的延長。

圖2 在100×100的區域內隨機生成100個節點的分布圖Fig.2 Map of one hundred node generated randomly in 100×100 region

3 結束語

圖3 平均能力消耗變化趨勢圖Fig.3 Change trends of the average power consumption

圖4 存活節點變化趨勢圖Fig.4 Change trends of the surviving node

文中提出了基于博弈論的有效分簇路由算法（GECR）算法，考慮到節點剩余能量和網絡能量均衡兩個因素，在簇頭節點產生算法和簇的形成這兩個方面對傳統的LEACH算法進行改進，仿真結果顯示，本算法能夠有效地使簇首節點合理分布，從而平衡網絡負載，節省節點能量，延長網絡壽命。

[1]王殊，胡富平，屈曉旭，等.無線傳感器網絡的理論及應用[M].北京：北京航空航天大學出版社，2007：73-94.

[2]楊璽.面向實時監測的無線傳感器網絡[M].北京：人民郵電出版社，2010：78-85.

[3]李光久.博弈論基礎教程[M].北京：化學工業出版社，2005：31-37.

[3]張盛開，張亞東.現代對策（博弈）論與工程決策方法[M].大連：東北財經大學出版社，2005：86-152.

[4]胡靜，沈連豐.基于博弈論的無線傳感器網絡分簇路由協議[J].東南大學學報，2010，40（3）:441-445.HU Jing，SHEN Lian-feng.Clustering routing protocol of wireless sensor networks based on game theory[J].Journal of Southeast University，2010， 40（3）:441-445.

[5]楊寧，田輝，黃平，等.基于博弈理論的無線傳感器網絡分布式節能路由算法[J].電子與信息學報，2008，30（5）:1231-1233.YANG Ning，TIAN Hui，HUANG Ping，et al.Distributed energy-economical routing algorithm based on game-theory for WSN[J].Journal of Electronics&Information Technology，2008，30（5）:1231-1233.

[6]馬昌鳳.最優化方法及其Matlab程序設計[M].北京：科學出版社，2010:60-150.