陳亦萍

(福州大學至誠學院計算機工程系，福建福州350002)

基于多人博弈的無線傳感器網絡簇內信息融合算法

陳亦萍

(福州大學至誠學院計算機工程系，福建福州350002)

利用多人博弈的思想對簇內節(jié)點間協(xié)作和競爭的關系進行分析，提出一種簇內信息融合算法。通過仿真實驗對節(jié)點能量消耗的均衡性、網絡生存周期及信息融合精度等方面進行性能評估驗證該算法的有效性。

無線傳感器網絡；數據融合；博弈論

無線傳感器網絡（wireless sensor networks，WSN）[1]為了獲取更加精確的感知信息，通常在監(jiān)測區(qū)域內部署高密集性的傳感器節(jié)點。如此大規(guī)模的部署導致大量冗余節(jié)點的存在，使得系統(tǒng)具有很強的容錯性同時大量節(jié)點能夠增大覆蓋的監(jiān)測區(qū)域減少盲區(qū)的存在。但是從通信能量角度而言，冗余節(jié)點的存在會消耗網絡資源，造成能源的浪費。密集性的節(jié)點部署導致同簇內相鄰近節(jié)點對同一監(jiān)測對象的感知信息中具有高度的相關性和冗余性。考慮到無線傳感器網絡受能量有限、帶寬受限等問題困擾，大量冗余節(jié)點的數據傳輸將會消耗大量的通信能量，并容易造成網絡的擁塞，浪費通信帶寬。因此對于能源受限制的無線傳感器網絡而言，通過研究更加合理有效的冗余節(jié)點處理機制和數據融合技術，減少網絡能源浪費對于延長網絡的生命周期有重要的意義[2-3]。

論文借鑒了博弈理論[4]對節(jié)點這種協(xié)作與冗余的關系進行分析，提出一種簇內基于多人博弈的信息融合優(yōu)化算法（an optimized algorithm of data fusion based on multi-players game theory，DFEAMG)。在保證網絡的覆蓋度、可用性及監(jiān)測信息精確度的前提下，DFEAMG有效地對簇內節(jié)點進行融合處理，減少了網絡中冗余、無效的數據傳輸，達到簇內節(jié)點能量消耗的優(yōu)化。

1 問題描述

在無線傳感器網絡分簇拓撲結構中，假設存在n個同質的傳感器被劃分為K個分簇結構分布在某一區(qū)域范圍內，它們彼此獨立對同一對象的同一屬性進行觀測，一個簇結構構成一個局部的融合系統(tǒng)。若某個簇結構有m個成員節(jié)點，對于第i成員節(jié)點，令Si表示其的傳輸策略，具體定義如公式（1），同時令Zi表示其在某一時刻的觀測值。為了簡化問題，簇首節(jié)點按公式（2）對收集到的數據采用均值融合。

同時,由節(jié)點能量消耗分析[1]可知，節(jié)點無線通信模塊消耗絕大部分能量并且當處在發(fā)送狀態(tài)時能量消耗最大?？梢酝ㄟ^減少簇內處在發(fā)送狀態(tài)的節(jié)點有效地對進行能量優(yōu)化。同時節(jié)點間通過協(xié)作提高融合結果的精確度、保證系統(tǒng)的容錯性，因此如何在保證不影響融合結果精確度的情況下，獲得簇內能耗優(yōu)化的傳輸方案是該算法研究的目標。

g1（X）代表簇內能量消耗量，其中Ωi是si的簇內鄰居節(jié)點的傳輸策略集，X表示局部融合系統(tǒng)內傳輸策略，p為懲罰常數。每個采樣周期中，對于同一監(jiān)測目標進行感知的簇內鄰居節(jié)點獲得的感知數據具有高度的相似性和冗余性。因此通過引入一個懲罰常數來調整簇內鄰居節(jié)點傳輸策略，減少冗余節(jié)點傳輸數據。

為了保證簇內均值融合結果的精確度，在簇首節(jié)點收集到的數據必須滿足最小偏差。這樣可以同時用于調整簇內鄰居節(jié)點的傳輸策略，防止過少的節(jié)點傳輸數據導致最后影響最后融合結果。g2(X)表示融合結果精確度，其中Zk表示按X傳輸策略傳輸獲得到數據集合。std為求標準偏差函數。

參與主體的效益函數定義式（5）：

w1、w2分別表示g1(x)和g2(x)的權重，代表算法中能量消耗和融合結果精確度之間的均衡關系，用于調整簇內節(jié)點的傳輸策略。

2 DFEAMG算法

2.1 算法思想

簇內多人博弈信息融合優(yōu)化算法(DFEAMG)通過對簇內節(jié)點關系進行分析，節(jié)點間的冗余和協(xié)作關系構成了博弈模型中的競爭和合作關系。算法試圖通過在簇內成員節(jié)點間以自適應方式尋求一種傳輸組合方式，對簇內節(jié)點消耗能量進行優(yōu)化并保證融合結果的精確度。將簇內成員節(jié)點相互競爭映射為多人博弈[5-7]，如何通過非合作博弈獲取最優(yōu)的收益的過程視為多人博弈的優(yōu)化過程即從非均衡狀態(tài)向均衡狀態(tài)的動態(tài)調整過程。在初始節(jié)點根據自身的剩余能量隨機做出決策，依賴于各節(jié)點最優(yōu)反映動態(tài)的學習思想，在重復博弈的過程中獲得個主體合理的決策分配從而實現(xiàn)融合結果的最優(yōu)化。

2.2 博弈結構

DFEAMG模型將融合系統(tǒng)與博弈過程進行了映射，能夠體現(xiàn)出簇內冗余環(huán)境中各節(jié)點策略選擇的過程。該博弈結構可以定義為：

其中，博弈主體集合I、策略集合S、收益μ、均衡擾動函數ξ及停止準則τ。對于一般的組合優(yōu)化問題，確定該算法的5個要素就可以轉化為一個純策略的多人非合作博弈問題。該算法中的5元素定義如下：

將局部融合系統(tǒng)中的每個傳感器節(jié)點i映射為一個參與博弈的主體，則所有同質傳感器節(jié)點構成博弈主體集合I=﹛1,2，…，n﹜，其中n為簇內成員節(jié)點數；si∈[0,1],i∈I表示博弈主體i的策略集，則在某一博弈回合中，主體選擇的策略si做出對應的傳輸策略，n個主體的策略組合s就對應于公式(5)中的一個候選解x；在簇內信息融合博弈中，為各博弈主體設置相通的效用函數，均為f(x)，即

當各個主體均無法選擇更優(yōu)的行動來更新系統(tǒng)狀態(tài)，即整個系統(tǒng)達到了納什均衡時。為了避免僅獲得局部最優(yōu)情況，通過隨機方式對該穩(wěn)定狀態(tài)進行擾動，使其再次回歸到不穩(wěn)定狀態(tài)。該文均衡擾動函數ξ定義如下：首先主體i通過rand(0,1)生成隨機數ai；接著比較ai與算法設定的擾動概率ρd，若ai＜ρd，則隨機選擇主體i的策略集中的一個元素，替換當前策略si；否則，維持原策略不變。所有主體經過上述過程后得到擾動后的新的策略組合s′。整個系統(tǒng)經過若干回合的從穩(wěn)定到不穩(wěn)定的擾動與恢復不斷重復，最后各博弈主體始終構成某一固定的策略組合，則該策略組合構成一定穩(wěn)定狀態(tài)。算法的停止準則τ采用指定的采樣周期停止算法。

根據關于Nash定理可知，局部融合博弈必存在至少一個Nash均衡點。即公式存在全局最優(yōu)解x*使得μi(s*)≥μi(s)，即f(x*)≥f(x)。顯然，全局最優(yōu)解并不是唯一的。這些全局最優(yōu)解構成集合﹛x*﹜，由其中的點構成的策略組合都能使得加權博弈達到Nash均衡狀態(tài)。當達到Nash均衡時，融合博弈中的各主體均獲得最優(yōu)的效用，這表示能通過計算得到一種最優(yōu)的節(jié)點傳輸組合方案，達到網絡效益最大。

2.3 DFEAMG算法流程

按一定規(guī)則獲得初始的融合博弈結構，包括博弈主體集、策略集和效用函數集的確定。對每個博弈主體，通過模仿、學習確定其在本輪博弈中的策略，并根據效用函數計算各主體的效用。博弈個體通過改變策略增加效用，并根據評估函數對本輪博弈局勢作出評價，判斷是否達到納什平衡，算法流程見圖1。

算法將簇內節(jié)點傳輸策略組合優(yōu)化問題的解空間映射到多人博弈的策略組合空間，通過主體的聯(lián)盟效用最大化行為達到一個納什均衡，并通過對均衡狀態(tài)施加擾動而重新到達均衡。納什均衡狀態(tài)下的問題解稱為納什均衡解。如果新的納什均衡解比上一回合尋找到的納什均衡解更優(yōu)，則更新，否則舍棄該解。通過上述的過程最終到達全局最優(yōu)解。這里系統(tǒng)狀態(tài)和效用函數是主體的共同知識，主體的理性行為指的是主體將會傾向于選擇使自己效用最大的策略。算法中“納什均衡解更優(yōu)?”的判斷是必要的，這樣下一個納什均衡解建立在前一個納什均衡解得基礎上。

圖1 算法流程圖

3 仿真實驗

3.1 實驗參數

通過采用MATLAB作為仿真平臺進行模擬實驗驗證DFEAMG算法的性能。為了簡化仿真實驗參數，假設前提如下：

（1）假設在較為理想的信道條件下忽略干擾和信號沖突等隨機因素的影響；

（2）假設節(jié)點一經部署完畢位置固定，節(jié)點能量小于（0.0000000001*Eo）則表示失效，無法進行工作；

（3）假設網絡中的有效節(jié)點剩余10％時網絡的覆蓋度和連通度大幅度減低，網絡不可用算法終止。

實驗參數如表1,能量消耗模型參照參考文獻[1]。

表1 實驗參數表

由于目前還沒有標準的通用的數據集，實驗首先利用自行構造的模擬數據驗證算法的可行性，從網絡生存周期，網絡能量消耗及融合結果精確度等，驗證DFEAMG算法的優(yōu)劣性。因為DFEAMG 是UCLC、MRPSO的改進算法，實驗只選擇LEACH，MRPSO作為對比算法。

實驗設定某一固定值為參考點，代表待觀測對象的真實值；用不同的百分比表示參與融合的各傳感器節(jié)點的觀測誤差范圍及鄰居節(jié)點相似度范圍。根據誤差概率，采用隨機的方法，產生圍繞固定值上下波動的數組，用以模擬表示若干個精度不同的傳感器節(jié)點在一定采樣周期中對同一對象的觀測數據。生成數據的主要參數包括實際測量參考值z、節(jié)點數n、采樣周期數m（隨機在網絡的生存周期中取出若干個測量數據比較）、各節(jié)點的誤差概率γ=﹛γ1，γ2，…，γn﹜和鄰居節(jié)點相似度λ= ﹛λ1，λ2，…，λn﹜

測試數據產生規(guī)則：每個采樣周期k（k=1,2，…，m），節(jié)點i（i=1,2，…，n）按如下規(guī)則產生模擬的測試數據zik：

則其鄰居節(jié)點j產生的測試數據如下：

3.2 實驗結果分析

在上述網絡仿真環(huán)境下，采用自行生成的模擬數據進行實驗。

實驗1比較的是DFEAMG、MRPSO、LEACH3種不同算法相應的網絡生存周期情況。圖2顯示的是網絡中失效節(jié)點的數量隨時間變化的情況。3個算法的網絡生命周期分別是1145、975、580左右。MRPSO的網絡生存周期比LEACH的延長了68％，而DFEAMG的比LEACH的延長了97％，將近一倍。DFEAMG算法比MRPSO的延長了170個生存周期左右。出現(xiàn)這種現(xiàn)象的原因是DFEAMG算法在MRPSO分簇路由中結合了簇內信息融合技術，不僅實現(xiàn)了簇間路由能量的優(yōu)化，更進一步減少簇內節(jié)點的能量消耗。從圖上可以看出MRPSO和DFEAMG的第一個節(jié)點和最后一個節(jié)點失效時間的跨度差不多，曲線都呈急速上升狀。這說明DFEAMG與MRPSO一樣，網絡中的節(jié)點實現(xiàn)了能耗均衡。

圖3描述的是從第475～525個采用周期中LEACH、MRPSO、DFEAMG 3種算法每輪網絡中節(jié)點能量消耗總和情況。由圖可知，采用LEACH算法的網絡能量平均消耗最高，每個周期能量消耗范圍[0.05,0075]，波動范圍最大。MRPSO每輪網絡中節(jié)點能量消耗總分布范圍在[0.048,0.054]，而DFEAMG的分布在[0.42,0.0475]。DFEAMG的能量消耗總和是3種算法中最少的，而且數值分布范圍最小。出現(xiàn)這種現(xiàn)象是因為MRPSO算法只有進行了簇間路由優(yōu)化減少簇首轉發(fā)數據的能耗，而DFEAMG通過簇內信息融合減少，減少了整個網絡的數據傳輸量，真正實現(xiàn)了整個網絡的能量優(yōu)化。

實驗2比較DFEAMG和MRPSO兩種不同算法經過數據融合后最終結果的相似度。實驗在網絡的生命周期內隨機抽取50個周期的融合數據進行對比。表2給出的是在不同允許的誤差范圍內兩種算法得到融合結果的相似度。假設z1、z2分別表示網絡采用DFEAMG和MRPSO算法進行融合后的最終感知數據。η表示這兩種感知數據之間的誤差，計算公式如(10)。

由表2可知，當誤差d≤0.0005*z是DFEAMG與MRPSO融合結果相似度為88％。當誤差為d≤0.001*z是DFEAMG與MRPSO融合結果相似度為98％。這證明了DFEAMG算法對系統(tǒng)融合結果的精確度并無很大影響。出現(xiàn)這種現(xiàn)象的原因是DFEAMG算法中參與數據融合的數據滿足最小偏差，這樣可以防止因為測量精度問題導致測量數據與其他節(jié)點的差別很大的節(jié)點參與數據融合影響最終的結果，從某種意義上說DFEAMG的最終融合比傳統(tǒng)的均值融合更貼近實際值。結合圖3可以證明DFEAMG不僅實現(xiàn)了簇內能量消耗優(yōu)化同時也保證了融合結果精確性。

圖2 網絡生存周期

圖3 每個周期能量消耗

表2 融合結果比較

4 小結

通過將簇內節(jié)點競爭傳輸過程映射為為同質傳感器間的多人博弈過程。DFEAMG僅依賴于當前各節(jié)點的觀測數據和鄰居節(jié)點的相關信息，克服了其他加權算法需要部分先驗知識以及具有主觀性的缺陷。實驗結果表明，算法很好的均衡了網絡中簇內能量消耗優(yōu)化問題與融合結果精確度的問題，實現(xiàn)了簇內能耗優(yōu)化，延長了網絡生存周期并同時保證了網絡融合結果的精確性。

[1]孫利民，李建中，陳渝，等．無線傳感器網絡[M].北京:清華大學出版社，2005．

[2]SHIH E,CHO SH,ICKES N,et al.Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks[C]//Proceedings of the 7th Annual International Conference on Mobile Computing and NetworkingRome：Association for Computing Machinery，2001.

[3]CRULLER D,ESTRIN D,SRIVASTAVA M.Overview of sensor networks[J].Computer(Long Beach,CA),2004,37 (8)：41-49.

[4]托馬斯L C.對策論及其應用[C].天津：解放軍出版社,1988.

[5]GILBOA I,MATSUI A.Social stability and equilibrium[J].Econometrical,1991,59：859-867.

[6]FELEGYHAZI M,HUBAUX J P,BUTTYAN L.Nash equilibria of packet forwarding strategies in wireless Ad hoc networks[J].IEEE Transactions on Mobile Computing，2006,5（5）:463-467.

[7]徐敏.基于博弈思想的優(yōu)化算法研究[D].合肥:中國科技技術大學,2005.

[8]RENITA MACHADO,SIRIN TEKINAY.A survey of game-theoretic approaches in wireless sensor networks[J]. Computer Networks，2008，52:3047–3061.

[9]VON NEUMMAN,MORGENSTERN O.Theory of games and economic behavior[M].2nd ed.Princeton：Princeton University Press,1947.

[10]GUPTA G,YOUNIS M.Load-balanced clustering of wireless sensor networks[J].Proceeding of IEEE International Conference on Communications,2003(3)：1848-1852.

[11]LI C F,CHEN G H,WU J.EECS：an energy efficient clustering scheme in wireless sensor networks[C]//The 24th IEEE International Performance,Computing,and Communications Conference,2005.

[12]AKYILDIZ I,SU W,SANKARASUBRAMANIAM Y,et al.Wireless sensor networks：a survey[J].Computer networks,2002,38(4)：393-422.

[13]DAVID C,DEBORAH E,MANI S.Overview of sensor network[J].IEEE Computer,2004,37(8)：41-49.

[14]張銳戈，陳善繼.基于寬帶源的單矢量傳感器參數估計[J].三明學院學報,2008,25(2)：154-157.

An Algorithm of Inter-cluster Data Aggregation Based on Multi-players Game Theory in Wireless Sensor Networks

CHEN Yi-ping
(Department of Computer Engineering,Zhicheng College,Fuzhou University,Fuzhou 350002,China)

Based on the analysis of the competition and cooperation between nodes by multi-players game theory,an algorithm of inter-cluster data aggregation is proposed in this paper.Simulations are taken to evaluate the performance of energy consumption balance,network lifetime and the precision of the aggregate data,and the results prove the effectiveness of this algorithm.

wireless sensor networks;data aggregation;game theory

TN929.5

A

1673-4343（2013）04-0024-06

2013-04-10

陳亦萍，女，福建莆田人，助教。研究方向:PSO智能算法、博弈論。