基于演化博弈論的無線傳感網監測節點分群算法

劉保見　張效義　李青

摘要：針對大規模無線傳感器網絡多輻射源定位中，輻射源公共覆蓋范圍內監測節點能耗過高造成網絡壽命降低的問題，提出一種基于演化博弈理論（EGT）的傳感網監測節點分群算法。通過將最優節點集的搜索空間映射到博弈的策略組合空間，以博弈的效用函數為目標函數構建了非合作博弈模型；利用納什均衡分析及均衡的擾動恢復過程實現目標優化；設計了分群算法以優化節點集組成相應的群參與最終的定位。以接收信號強度指示（RSSI）/信號到達時間差（TDOA）兩輪定位為例，將該算法與典型的最近鄰算法、基于離散粒子群優化（DPSO）的分群算法在定位精度和網絡壽命方面作對比。仿真結果表明，該分群算法避免了多輻射源公共覆蓋區域內節點能耗較高的問題，延長了網絡壽命，同時保證了對輻射源的定位。

關鍵詞：無線傳感器網絡；多輻射源定位；分群算法；演化博弈論；納什均衡；網絡壽命；定位精度

中圖分類號：TP393.02

文獻標志碼：A

0引言

隨著微機電技術與無線通信技術的迅猛發展，無線傳感器網絡（Wireless Sensor Network， WSN）被廣泛應用于環境監測、智能家居、空間探索以及目標定位跟蹤等領域[1]。特別是網絡的分布式信息處理、抗毀性強、快速展開等特點，使得WSN成為輻射源定位的有效手段和方法[2-4]。與傳統的單節點定位方法相比較，基于WSN的分布式輻射源定位方法具有定位精度高、廉價、可靠以及隱蔽性強等優勢。網絡化監測的另一優勢是同時實現多輻射源定位，但是當監測區域內出現多個輻射源節點且各輻射源節點具有公共覆蓋區時，如何對監測節點進行分群實現網絡能耗與定位精度整體最優，同時避免多輻射源公共覆蓋范圍內節點能耗增加，是實現多輻射源定位的核心問題之一。

在現有的面向定位的無線傳感器網絡分群算法研究中，對于多輻射源定位的應用，特別是輻射源節點之間的覆蓋區域存在交疊時，一個監測節點可能監測到多個輻射源的輻射信號，致使其能耗消耗過快，出現過早死亡，從而影響網絡的壽命。為保證節點的能耗均衡以及盡可能地延長網絡的壽命，應當盡量避免多輻射源公共覆蓋區域內的節點同時服務于多個輻射源的定位。在文獻[5-8]等相關文獻中給出了相應的彈性神經網絡算法、改進粒子群算法等來優化多輻射源定位中公共區域內的節點服務于多個輻射源定位的情況。然而，在上述方法中沒有考慮參與定位節點的個數以及監測節點相對于輻射源的位置對定位精度的影響，僅簡單地將參與定位的節點個數定為3個，選擇距離輻射源位置較近的節點參與定位。

但是，基于多點聯合定位的定位精度與監測節點的分布有密切的關系[9]，優化選取合適位置的節點組成群將有助于提高對輻射源的定位精度。文獻[10]給出了一種基于離散粒子群優化（Discrete Particle Swarm Optimization， DPSO）的分群算法，雖然在最優節點集選取的過程中考慮了節點的幾何分布對定位精度的影響，但是該分群算法針對的是單輻射源情況，未考慮多輻射源情況下公共區域內節點能耗較高的問題。

在WSN中，監測節點通常隨機大規模地布設在監測區域內，在多輻射源個數已知的情況下，如何進行分群在避免多輻射源公共覆蓋區域內節點能耗較高、延長網絡壽命的同時為定位提供服務是本文所要研究問題的關鍵。

本文針對WSN中多輻射源公共覆蓋區域內的節點能耗較高的問題，基于演化博弈論（Evolutionary Game Theory， EGT）提出了一種面向多輻射源定位的分群算法。首先，建立了問題的數學模型，并將求解的問題模型映射到博弈的模型空間；然后，利用演化博弈論方法求解出全局最優節點集；最后，對最優節點集內的節點再次利用博弈論方法進行群首選取，最終實現了面向多輻射源定位的分群算法。仿真結果表明，該方法在保證對輻射源的定位精度的同時避免了多輻射源覆蓋區域內節點能耗較高的問題，延長了網絡壽命。

1問題描述

在實際的應用中，監測區域內通常出現多個且移動輻射源節點的情況。多輻射源公共覆蓋區域內節點能耗較高的問題也即所謂的“熱點”問題，將影響網絡的壽命與定位功能。如圖1所示，在監測區域內出現兩個輻射源節點[T1，T2]，節點集{S1，S2，S3，S4}為兩輻射源節點公共覆蓋區域內的節點，為避免公共覆蓋區域內節點能耗較快，需確定公共區域內的節點參與到哪個輻射源的監測。為此，本文提出了一種面向多輻射源定位的分群算法，以在保證網絡低能耗、高精度定位的同時避免公共覆蓋區域內的“熱點”問題。

1.2群定位精度模型

監測節點的幾何分布對目標輻射源定位精度的影響通常采用幾何精度稀釋因子（Geometry Dilution Of Precision， GDOP）來衡量。GDOP值越小，定位精度越高。依據文獻[11]中給出的GDOP表達式，將監測節點位置對定位精度的影響轉化為監測節點相對于輻射源節點角度之間的關系，并對表達式進行進一步的推導，給出了影響GDOP值（記為f2）的主要因素。

1.3網絡能耗均衡模型

在WSN中，要延長網絡壽命，減少網絡能耗只是其中的一方面，另一方面則是保證網絡能耗的均衡，也即避免網絡中出現“熱點”問題。為保證網絡能耗的均衡，這里將以節點i的剩余能量Eni作為能耗均衡的指標。同時，采用Sigmoid函數將節點能耗均衡指標映射到區間[0，0.5]中，其表達式如式（6）所示：

2基于演化博弈論的節點集優化算法

博弈論是一種研究決策主體的行為發生直接相互作用時的決策以及這種決策的均衡問題的理論[12]。即“理性的”個體在其他參與者策略選定的情況下，如何使得自己的利益最大化的最優反映。博弈論通常包含以下幾個要素：參與者、行動、信息、策略、效用、結果和均衡，其中參與者、策略和效用是一個博弈所必需的要素。

演化博弈論是一種動態的博弈過程，其思想來源于自然界生物進化的理論，博弈主體按照一定的規則進行策略的調整。“有限理性”的參與人在博弈的過程中不斷學習，選擇自己的最優策略。在分析判斷博弈方的選擇和博弈結果的方法中通常采用納什均衡分析。

針對第一章中問題的描述，面向多輻射源定位的分群算法本質上是在避免公共區域內節點能耗較高情況下的組合優化問題，而博弈論主要用來解決博弈各方存在利益沖突的理論。如果將最優節點集的搜索空間映射為博弈的策略組合空間，將目標函數映射為博弈的效用函數，則優化問題的求解過程就變換為在博弈空間的上下文中，博弈主體尋求最優效用的策略組合的演化博弈過程。

3面向多輻射源定位的分群算法

在給定各輻射源輻射信號體制不同的情形下，本文提出的分群算法中充分考慮了監測節點的分布對定位精度的影響，使得分群在滿足網絡低能耗的同時為定位提供服務。為進一步提高網絡能量的利用率，定義該分群算法為基于事件觸發的分群過程，也即只有在監測區域內出現輻射源節點時才會觸發相應的分群。同時，為保證節點有充足的時間進行定位，本文約定完成一次精確定位為一輪（如圖3所示）。在每輪定位過程中，主要包含臨時中心選取、接收信號強度指示（Received Signal Strength Indication， RSSI）粗定位、面向定位的分群和TDOA定位四個主要部分。其中，面向定位的分群又分為：最優節點集的選取、群首選取以及數據傳輸。

當監測區域內出現輻射源節點時，則觸發相應的分群過程。為避免網絡中數據遠距離傳輸所帶來的能耗增加的問題，在每輪一開始，輻射源覆蓋范圍內的監測節點依據剩余能量最大準則選舉出臨時中心節點。各監測節點將監測到的輻射源信息以及自身的坐標信息發送給臨時中心節點；臨時中心節點利用數據關聯算法[13]對獲得的輻射源數據進行聚類分析從而得出輻射源的個數，并對具有不同信號特征的輻射源節點分別進行標記，進而將監測節點與相應的輻射源節點進行關聯。

由于監測節點相對于輻射源的分布影響最終的定位精度，為便于面向定位的分群過程中最優節點集的選取，本文算法需要知道輻射源的粗略位置。本文中采用了能耗較低的RSSI定位方法。輻射源覆蓋范圍內的監測節點將其坐標、監測到的輻射源的數據以及自身的剩余能量發送給臨時中心節點，臨時中心節點在進行完數據聚合后，執行RSSI定位解算算法獲得各輻射源粗略的位置。

3.1最優節點集選取

在獲得各輻射源的粗略位置后，臨時中心節點利用第2章中基于演化博弈論的方法進行最優節點集的選取。博弈的主體為輻射源覆蓋范圍內的監測節點；臨時中心節點利用前期數據關聯的結果，獲得每個監測節點所監測到的輻射源節點集，也即是各個博弈主體的策略集；效用函數部分則綜合考慮網絡能耗、定位精度以及能耗均衡等因素。在獲得最優節點集后，對參與同一輻射源節點定位的最優節點集，利用數據聚合過程中輻射源信號特征的不同進行相應的標記。

3.2群首選取

在群首選取階段，主要是將最優節點集選取階段所選取的具有相同特征標識的最優節點集組成同一個群參與最終的定位。由于在WSN中，計算所消耗的能量遠遠小于節點之間通信所消耗的能量。為此，對群首節點的選取，同樣采用博弈論的方法進行博弈。博弈的主體為參與同一輻射源定位的最優節點集。各博弈主體的策略集為：成為群首節點或成為成員節點，分別用1、0來表示；效用函數則綜合考慮了節點的剩余能量、到臨時中心節點的距離以及群能耗等因素。具體定義如式（10）：

其中：C為一常數；Eni表示節點i的剩余能量；Enave表示最優節點集內節點的平均剩余能量；dtoCenter（i）表示節點i到臨時中心節點的距離；dmax_toCenter表示最優節點集中的節點到臨時中心節點的最大距離；di， j表示節點i到節點j之間的距離；

合理情況是指相應的策略集中僅有一個節點為群首，不合理情況指相應的策略集中沒有或有多個節點為群首節點。

為簡化計算，這里利用節點之間的距離來代替兩節點之間通信所消耗的能量。

在確定各節點集中的群首后，臨時中心節點將各監測節點的坐標與相應的分群結果信息（包含是否為群首以及參與哪類特征輻射源的定位）組合為廣播消息，并將該消息在輻射源覆蓋范圍內進行廣播。監測節點在接收到臨時中心節點所廣播的消息后，通過比對自身的坐標信息來獲得相應分群結果信息，從而確定自己是否參與定位、參與到哪類輻射源信號特征的定位以及是否為群首。最終，使得具有同一特征標記的最優節點集組成一個群參與相應特征信息輻射源節點的定位。

3.3數據傳輸及TDOA定位

在完成相應的分群后，則對相應的輻射源進行監測。各監測節點將監測到的輻射源的信號與分群過程中給出的信號的特征相比較，若相同，則接收相應的輻射源信號，否則丟棄相應的輻射源信號。這樣避免了多輻射源覆蓋范圍內的節點服務于多個輻射源而導致能耗消耗過快的問題。各群首節點將監測到的輻射源的信號在群內進行廣播，成員節點在接收到相應信息后與自己監測到的輻射源信號相比較進行相應的時差估計，并將估計的結果發送給相應的群首；群首在得到相應的時差估計值后執行Chan氏算法進行相應的定位解算，最終確定輻射源的位置。各群首節點將TDOA定位的輻射源位置信息發送給臨時中心節點；臨時中心節點在接收到所有輻射源的位置信息后，進行相應的數據壓縮并將壓縮的結果發送給Sink節點。具體的路由協議可以采用AODV（Ad hoc On-demand Distance Vector routing）、Dijkstra等典型的無線路由協議。

4仿真分析

在Matlab 7.0環境下對本文提出的算法進行了仿真，仿真中設定監測區域為100m×100m，在監測區域內隨機布設150個監測節點，Sink節點的位置在監測區域內隨機初始化，為簡化數據關聯部分的工作，監測區域內輻射源的個數已知。為均衡目標函數中各因素的權重，給定相應定位精度、網絡能耗、能耗均衡的權值系數分別為[0.3，0.3，0.4]。其他詳細的參數如表1所示。

在監測區域內布設兩個輻射源節點，并且兩輻射源節點公共覆蓋范圍存在多個監測節點情況下，運行本文提出的分群算法，分群結果如圖4所示。其中，[s1，s2，s3]所組成的群用于監測輻射源T1；[s4，s5，s6]所組成的群用于監測輻射源T2。從分群結果上可以看出，本文提出的算法避免了公共覆蓋區域內的監測節點服務于多個輻射源。

為比較算法的性能，本文主要從網絡能耗和定位精度兩個方面，將本文提出的算法與經典的最近鄰法[14]（選擇距離目標最近的3個節點組成群參與對輻射源的定位）和基于離散粒子群優化（Discrete Particle Swarm Optimization， DPSO）的分群算法作對比。

相應的性能指標使用網絡壽命，即網絡從開始運行到第一個節點死亡時網絡所運行的輪數。

4.1網絡壽命

首先針對監測區域內布設兩個輻射源節點的情況對算法網絡壽命進行仿真；其次，在給定場景下仿真不同輻射源個數對三種算法網絡壽命的影響。

仿真結果分別如圖5和圖6所示。

由圖5可以看出，本文提出的算法相比基于DPSO的分群算法、最近鄰算法延長了網絡的壽命。一方面是由于在最優節點集選取的過程中，本文算法是從整體能耗及定位精度的角度選取最優位置的節點參與定位，同時避免了多輻射源公共覆蓋區域內一個監測節點服務于多個輻射源節點的情況，減少了其能耗，從而延長了網絡壽命；另一方面，在群首選取的過程中，不僅考慮了節點的剩余能量、距離臨時中心節點的遠近，還考慮了群的能耗，進一步減少了網絡能耗。最近鄰算法由于沒有考慮能耗等因素，因此，同等條件下其網絡壽命較短；同時，由于沒有考慮網絡的能耗均衡，其第一個節點死亡到最后無法定位之間的時間間隔較長。

由圖6可以看出，隨著輻射源個數的增加，本文提出的分群算法與基于DPSO的分群算法的網絡壽命均在逐漸減小。這是由于在給定場景下，輻射源節點個數的增加降低了網絡能耗的均衡性，從而減少了網絡壽命。而最近鄰算法在分群的過程中沒有考慮網絡的能耗均衡，因此，輻射源節點個數的增加對該算法下的網絡壽命影響不大。同時可以看出在輻射源個數相同的情況下，本文提出的分群算法在延長網絡壽命方面要優于基于DPSO的分群算法和最近鄰算法。這也進一步驗證了該算法避免了多輻射源公共覆蓋區域內節點能耗較高的問題，延長了網絡壽命。

4.2定位精度

首先針對監測區域內布設兩個輻射源節點的情況分別對三種算法的定位精度進行20輪仿真，每一輪中進行100次仿真并將仿真的結果求取平均值作為該輪的仿真值；其次，在給定場景下仿真不同輻射源個數對算法定位精度的影響。仿真結果分別如圖7和圖8所示。

由圖7可以看出基于DPSO的分群算法的平均GDOP值小于本文提出的分群算法，也即基于DPSO的分群算法的定位精度要略優于本文提出的算法。

然而，基于DPSO的分群算法其定位精度值波動較大，而本文提出的分群算法的定位精度值基本維持在穩定值。這是由于本文提出的算法在優化節點選取的過程中考慮了多輻射源覆蓋區域內節點能耗較高的問題，從整體能耗以及定位精度均衡的角度選取最優面向定位的節點集；而基于DPSO優化的面向定位的分群算法則是對單個輻射源分別進行優化，并且在最優節點選取的過程中并未考慮公共區域內節點能耗較高的問題。最近鄰算法由于既沒有考慮公共區域內的節點能耗較高的問題也沒考慮節點的位置對定位精度的影響，因此，其定位精度要差于上述兩種算法。

由圖8可以看出隨著輻射源個數的增加，平均GDOP值都在增加，也即對輻射源的平均定位精度在逐漸降低。這是由于給定監測節點布設場景的情況下，輻射源個數的增加等價于輻射源個數不變的情況下監測節點個數的減少，因此，限制了最優節點集的選取，最終導致平均定位精度的降低。同時，可以看出在相同輻射源個數的情況下，本文提出的算法在定位精度方面略差于基于DPSO的分群算法而優于最近鄰算法，進一步驗證了本文提出的算法是從整體能耗以及定位精度的角度選取面向定位的最優節點集。因此，本文提出的算法在犧牲部分群定位精度的同時延長了網絡壽命。

5結語

在節點能耗受限且隨機大規模布設的WSN中，給出了一種面向多輻射源定位的分群算法。與經典的最近鄰算法、基于DPSO優化的面向定位的分群算法相比，基于演化博弈論的分群算法在犧牲部分群定位精度的同時避免了多輻射源公共覆蓋區域內節點服務與多個輻射源的情況，從而延長了網絡壽命。

雖然本文算法在避免多輻射源公共覆蓋區域內節點能耗較高以及延長網絡壽命方面展現了較好的性能，但是，該算法僅考慮了群內單跳通信的情形，為進一步延長網絡的壽命，下一步的工作將考慮群內多跳通信的情形并對算法作出相應的改進，使其適應于更廣的應用場合。

參考文獻：

[1]KONG J-I， KIM J-W， EOM D-S. Energy-aware distributed clustering algorithm for improving network performance in WSNs [J]. International Journal of Distributed Sensor Networks， 2014（5）： 1-10.

[2]PRABHAVATHI M， RAJESHWARI R. Cluster-based mobility management for target tracking in mobile sensor networks [C]// ICoAC 2011： Proceedings of the 2011 Third International Conference on Advanced Computing. Piscataway， NJ： IEEE， 2011：198-203.

[3]HOANG H G， VO B T. Sensor management for multi-target tracking via multi-Bernoulli filtering [J]. Automatica， 2014， 50（4）： 1135-1142.

[4]ARMAGHANI F R， GONDAL I， KAMRUZZAMAN J， et al. Sensor selection for tracking multiple groups of targets [J]. Journal of Network and Computer Applications， 2014， 46： 36-47.

[5]劉美，黃道平.WSN中傳感器節點的彈性神經網絡任務分配方法[J].華南理工大學學報（自然科學版），2010，38（6）：66-72. （LIU M， HUANG D P. Task allocation method of sensor nodes based on MEMSOM neural network in WSN[J]. Journal of South China University of Technology （Natural Science Edition）， 2010， 38（6）：66-72.）

[6]劉梅，權太范，姚天賓，等.多傳感器多目標無源定位跟蹤算法研究[J].電子學報，2006，34（6）：991-995. （LIU M， QUAN T F， YAO T B， et al. Multi-sensor multi-target passive locating and tracking[J]. Acta Electronica Sinica， 2006， 34（6）： 991-995.）

[7]LIU J， REN X， MA H. Adaptive swarm optimization for locating and tracking multiple targets [J]. Applied Soft Computing， 2012， 12（11）： 3656-3670.

[8]THIDA M， ENG H-L， MONEKOSSO D N， et al. A particle swarm optimisation algorithm with interactive swarms for tracking multiple targets [J]. Applied Soft Computing， 2013， 13（6）： 3106-3117.

[9]LEVANON N. Lowest GDOP in 2-D scenarios [J]. IEE Proceedings — Radar， Sonar and Navigation， 2000， 147（3）： 149-155.

[10]LIU B， LI Q， ZHANG X. DPSO based clustering algorithm for location in wireless sensor networks [J]. International Journal of Computer and Communication Engineering. 2016， 5（4）： 260-268.

[11]QUAN Q. Low bounds of the GDOP in absolute-range based 2-D wireless location systems [C]// ICIDT 2012： Proceedings of the 2012 8th International Conference on Information Science and Digital Content Technology. Piscataway， NJ： IEEE， 2012： 135-138.

[12]趙昕，張新.基于博弈論的無線傳感器網絡簇間路由選擇算法[J].計算機應用，2013，33（7）：1813-1815. （ZHAO X， ZHANG X. Inter-cluster routing algorithm in wireless sensor network based on game theory[J]. Journal of Computer Applications， 2013， 33（7）： 1477-1480.）

[13]謝宇，程維明.一種基于類間距閾值的模糊聚類算法[J].計算機應用與軟件，2008，25（9）：248-249. （XIE Y， CHENG W M. A fuzzy clustering algorithm based on the threshold of clusters interval [J]. Computer Applications & Software， 2008， 25（9）： 248-249.）

[14]TSENG Y-C， KUO S-P， LEE H-W， et al. Location tracking in a wireless sensor network by mobile Agents and its data fusion strategies [J]. The Computer Journal， 2004， 47（4）： 448-460.http：//comjnl.oxfordjournals.org/content/47/4/448.abstract

IPSN 03： Proceedings of the 2nd International Conference on Information Processing in Sensor Networks， LNCS 2634. Berlin： Springer-Verlag， 2003： 625-641.