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

孫艷琴，熊慶國(guó)

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

無(wú)線傳感器網(wǎng)絡(luò)包含了大量無(wú)線傳感節(jié)點(diǎn)。數(shù)字電路、無(wú)線通信、電池制造技術(shù)和微機(jī)電系統(tǒng)技術(shù)的進(jìn)步使無(wú)線傳感器節(jié)點(diǎn)變得更小、更廉價(jià)、功能更強(qiáng)大且更可靠，同時(shí)節(jié)點(diǎn)的壽命也逐漸延長(zhǎng)。由于在許多情況下無(wú)線傳感器節(jié)點(diǎn)無(wú)法從外界獲取能量也無(wú)法更換電池，因此，無(wú)線傳感器網(wǎng)絡(luò)的持續(xù)工作能力常依賴于無(wú)線傳感節(jié)點(diǎn)的電池容量。另外，絕大多數(shù)無(wú)線傳感器網(wǎng)絡(luò)使用多跳通信來(lái)避免高能耗、長(zhǎng)距離傳輸。每個(gè)傳感器節(jié)點(diǎn)直接與領(lǐng)域節(jié)點(diǎn)通信。因此單個(gè)節(jié)點(diǎn)能力不足將加重其領(lǐng)域節(jié)點(diǎn)的通信負(fù)擔(dān)，從而使部分區(qū)域節(jié)點(diǎn)的能量很快消盡，最終使整個(gè)無(wú)線傳感器網(wǎng)絡(luò)失效。

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

圖1 分簇多跳網(wǎng)絡(luò)Fig.1 Cluster-based multi-hop network

LEACH[2]（Low EnergyAdaptiveClusteringHierarchyProtocol）是第一個(gè)基于分簇的路由協(xié)議，基本思想是網(wǎng)絡(luò)中的節(jié)點(diǎn)自組組織成簇，在簇結(jié)構(gòu)中，簇首要收集簇內(nèi)節(jié)點(diǎn)采集的數(shù)據(jù)，同時(shí)還要承擔(dān)路由功能，將簇內(nèi)節(jié)點(diǎn)的冗余數(shù)據(jù)融合處理后再轉(zhuǎn)發(fā)給基站。LEACH隨機(jī)循環(huán)選擇簇頭結(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)結(jié)點(diǎn)，從而降低網(wǎng)絡(luò)能量消耗，延長(zhǎng)網(wǎng)絡(luò)生命周期，但是這種隨機(jī)產(chǎn)生的方式存在以下的缺陷：

1）不能保證簇頭節(jié)點(diǎn)的均勻分布，不能保證簇的規(guī)模的合理性，可能出現(xiàn)的情況是：符點(diǎn)密集的地方簇頭節(jié)點(diǎn)多，如果產(chǎn)生了多個(gè)簇頭節(jié)點(diǎn)，會(huì)產(chǎn)生冗余，造成能量的不合理消耗，從而影響網(wǎng)絡(luò)壽命；節(jié)點(diǎn)稀疏的地方簇頭節(jié)點(diǎn)少或者沒有產(chǎn)生簇頭節(jié)點(diǎn)，那么部分節(jié)點(diǎn)可能沒有簇頭節(jié)點(diǎn)，將造成網(wǎng)絡(luò)的不完全連通。

2）在LEACH算法中，節(jié)點(diǎn)根據(jù)自身通信代價(jià)最小原則選擇加入哪個(gè)簇，但是這種方式不能保證簇的負(fù)載平衡，因?yàn)闆]有考慮到遠(yuǎn)離基站較遠(yuǎn)的簇頭能量耗費(fèi)過快的問題。

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

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

1.1 網(wǎng)絡(luò)模型的構(gòu)建

無(wú)線傳感器網(wǎng)絡(luò)模型[5]基于以下假設(shè)：

1）N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在一個(gè)m×m的正方形區(qū)域內(nèi)，節(jié)點(diǎn)總有數(shù)據(jù)傳送到基站，基站遠(yuǎn)離監(jiān)測(cè)區(qū)域并用于接入到有線網(wǎng)絡(luò)或者蜂窩無(wú)線網(wǎng)絡(luò)。

2）每個(gè)節(jié)點(diǎn)具有唯一ID，為了避免網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁改變，假定節(jié)點(diǎn)部署后不再移動(dòng)，基站惟一且位置固定。

3）每個(gè)節(jié)點(diǎn)都具有相同的處理和通信能力，在網(wǎng)絡(luò)中的地位平等。

4）每個(gè)節(jié)點(diǎn)都具備數(shù)據(jù)融合處理功能，節(jié)點(diǎn)之間連接對(duì)稱。

5）每個(gè)節(jié)點(diǎn)可以根據(jù)它與接收者的距離遠(yuǎn)近，自由調(diào)整發(fā)射功率以節(jié)省能量。

6）網(wǎng)絡(luò)節(jié)點(diǎn)組織成簇結(jié)構(gòu)的形式，簇首執(zhí)行數(shù)據(jù)融合處理以減少簇內(nèi)節(jié)點(diǎn)產(chǎn)生的冗余數(shù)據(jù)，并負(fù)責(zé)將集中后的數(shù)據(jù)傳輸?shù)交尽?/p>

1.2 建立節(jié)點(diǎn)支付方程

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

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

1.3 決策過程

1）利用博弈思想建立網(wǎng)絡(luò)模型，包括：參與人集合S{s1，s2，…sn}；所有節(jié)點(diǎn)在某個(gè)時(shí)刻的策略所構(gòu)成的策略集L{l1，l2，…ln}；以及節(jié)點(diǎn)i成為簇首時(shí)的支付函數(shù)A；

2）每一個(gè)節(jié)點(diǎn)建立鄰節(jié)點(diǎn)信息集合，并廣播A值；

3）接收到鄰節(jié)點(diǎn)A值的節(jié)點(diǎn)，將其與自身A值進(jìn)行比較，并將大于自身A值的鄰節(jié)點(diǎn)記錄到鄰節(jié)點(diǎn)信息集中；

4）如果節(jié)點(diǎn)的鄰節(jié)點(diǎn)信息集為空，則自動(dòng)成為簇首，并廣播簇首選擇信息；接收到一個(gè)或多個(gè)簇首選擇信息的鄰節(jié)點(diǎn)，發(fā)送歸屬信息加入A值最大的簇首節(jié)點(diǎn)，此時(shí)若多個(gè)簇首選擇信息中的簇首節(jié)點(diǎn)具有相同的A值，則隨機(jī)選擇一個(gè)作為歸屬簇并發(fā)送歸屬信息；

5）如果無(wú)線傳感器節(jié)點(diǎn)收到了來(lái)自自身鄰節(jié)點(diǎn)信息集中某個(gè)節(jié)點(diǎn)發(fā)送的歸屬信息，卻沒收到任何簇首選擇信息，則表明該節(jié)點(diǎn)不在任何已生成簇首的傳輸范圍之內(nèi)，該節(jié)點(diǎn)將由鄰節(jié)點(diǎn)信息集中刪去已有歸屬簇的鄰節(jié)點(diǎn)，并回到4）；

6）當(dāng)所有參與人均決定自身策略后，并開始數(shù)據(jù)傳輸。

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

2 仿真分析

2.1 參數(shù)設(shè)置

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

圖2 在100×100的區(qū)域內(nèi)隨機(jī)生成100個(gè)節(jié)點(diǎn)的分布圖Fig.2 Map of one hundred node generated randomly in 100×100 region

3 結(jié)束語(yǔ)

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

圖4 存活節(jié)點(diǎn)變化趨勢(shì)圖Fig.4 Change trends of the surviving node

文中提出了基于博弈論的有效分簇路由算法（GECR）算法，考慮到節(jié)點(diǎn)剩余能量和網(wǎng)絡(luò)能量均衡兩個(gè)因素，在簇頭節(jié)點(diǎn)產(chǎn)生算法和簇的形成這兩個(gè)方面對(duì)傳統(tǒng)的LEACH算法進(jìn)行改進(jìn)，仿真結(jié)果顯示，本算法能夠有效地使簇首節(jié)點(diǎn)合理分布，從而平衡網(wǎng)絡(luò)負(fù)載，節(jié)省節(jié)點(diǎn)能量，延長(zhǎng)網(wǎng)絡(luò)壽命。

[1]王殊，胡富平，屈曉旭，等.無(wú)線傳感器網(wǎng)絡(luò)的理論及應(yīng)用[M].北京：北京航空航天大學(xué)出版社，2007：73-94.

[2]楊璽.面向?qū)崟r(shí)監(jiān)測(cè)的無(wú)線傳感器網(wǎng)絡(luò)[M].北京：人民郵電出版社，2010：78-85.

[3]李光久.博弈論基礎(chǔ)教程[M].北京：化學(xué)工業(yè)出版社，2005：31-37.

[3]張盛開，張亞東.現(xiàn)代對(duì)策（博弈）論與工程決策方法[M].大連：東北財(cái)經(jīng)大學(xué)出版社，2005：86-152.

[4]胡靜，沈連豐.基于博弈論的無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].東南大學(xué)學(xué)報(bào)，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]楊寧，田輝，黃平，等.基于博弈理論的無(wú)線傳感器網(wǎng)絡(luò)分布式節(jié)能路由算法[J].電子與信息學(xué)報(bào)，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]馬昌鳳.最優(yōu)化方法及其Matlab程序設(shè)計(jì)[M].北京：科學(xué)出版社，2010:60-150.