基于博弈論的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院 廣州 510006）

摘 要：為了有效解決無線傳感器網(wǎng)絡(luò)路由節(jié)能問題，引入了博弈理論思想，提出了一種基于博弈論的無線傳感器網(wǎng)絡(luò)非均勻分簇節(jié)能路由算法UCEER。仿真實(shí)驗(yàn)結(jié)果表明，該算法解決了節(jié)點(diǎn)能耗分布不均的難題，體現(xiàn)出了其自適應(yīng)調(diào)整簇首、調(diào)節(jié)節(jié)點(diǎn)負(fù)荷、延長網(wǎng)絡(luò)平均壽命的能力，保證了路徑的可靠度。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；博弈論；路由；非均勻分簇；節(jié)能

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)05-1865-03

Unequal clustering energyeconomical routing algorithm

based on gametheory for WSN

ZHONG Liusheng CHENG Lianglun

(Facaulty of Automation Guangdong University of Technology Guangzhou 510006 China)

Abstract:In order to efficiently solve the problem of rooting，this paper introduced the thinking of game theory and presented UCEER algorithm for wireless sensor networks. Simulation results show that the routing algorithm efficiently balances the energy consumption of nodes in wireless sensor networks prolongs the network lifetime and guarantees the path reliability.

Key words:wireless sensor networks; gametheory; routing; unequal clustering; energyeconomical

0 引言

隨著傳感器技術(shù)和通信技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)技術(shù)開始提出，并因其應(yīng)用的廣泛性而得到越來越多的重視。無線傳感器網(wǎng)絡(luò)是由一組傳感器節(jié)點(diǎn)通過無線介質(zhì)連接構(gòu)成的無線網(wǎng)絡(luò) 它采用Ad hoc方式配置大量微型的智能傳感節(jié)點(diǎn) 通過節(jié)點(diǎn)的協(xié)同工作來采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中的目標(biāo)信息^[1]。該網(wǎng)絡(luò)功耗低、成本低、體積小；集數(shù)據(jù)采集、處理、傳輸于一體 具有自組織特性和高抗毀能力 在地理環(huán)境監(jiān)測(cè)、災(zāi)害預(yù)報(bào)、醫(yī)療保健、工業(yè)生產(chǎn)過程監(jiān)測(cè)、惡劣環(huán)境監(jiān)測(cè)、軍事偵察等方面具有廣闊的應(yīng)用前景^[2]。無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的能量資源、計(jì)算能力和帶寬均非常有限，且節(jié)點(diǎn)十分密集，設(shè)計(jì)有效的策略延長網(wǎng)絡(luò)的生命周期成為無線傳感器網(wǎng)絡(luò)的首要問題。路由協(xié)議是網(wǎng)絡(luò)節(jié)點(diǎn)相互通信的基礎(chǔ)，無線傳感器網(wǎng)絡(luò)路由協(xié)議負(fù)責(zé)尋找一條傳輸路徑 將數(shù)據(jù)分組從數(shù)據(jù)源節(jié)點(diǎn)通過網(wǎng)絡(luò)多跳轉(zhuǎn)發(fā)至目標(biāo)節(jié)點(diǎn)^[3]。設(shè)計(jì)合理的路由協(xié)議對(duì)降低及平衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗，延長網(wǎng)絡(luò)的存活時(shí)間有著重要意義。

本文引入博弈理論思想，設(shè)計(jì)了一種非均勻分簇節(jié)能路由協(xié)議。盡管針對(duì)基于博弈論的路由協(xié)議已經(jīng)有了一定的研究，然而大部分路由協(xié)議，如文獻(xiàn)[4，5]均針對(duì)平面型網(wǎng)絡(luò)而設(shè)計(jì)；針對(duì)無線傳感器網(wǎng)絡(luò)分層型路由的研究中，文獻(xiàn)[6]設(shè)計(jì)了一種動(dòng)態(tài)、能量有效的層次分簇算法，該算法僅考慮了節(jié)點(diǎn)能量，并沒有同時(shí)考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中的分布，具有一定的局限性。

本文所提出的非均勻分簇節(jié)能路由算法（unequal clustering energyeconomical routing，UCEER）在無須任何定位裝置或定位算法的前提條件下，綜合考慮節(jié)點(diǎn)剩余能量、路徑的可靠度以及節(jié)點(diǎn)在網(wǎng)絡(luò)中的分布，選出具有較高能量，且簇內(nèi)傳輸損耗較小的節(jié)點(diǎn)作為簇首，從而延長整個(gè)傳感器網(wǎng)絡(luò)的生命周期。

1 無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)路由博弈模型

1.1 博弈論簡介

博弈論以決策主體的理性為分析的出發(fā)點(diǎn)，研究交互式條件下最優(yōu)理性決策，即決策主體的偏好能獲得最大滿足時(shí)的策略。如果僅有一個(gè)決策主體，即簡單的解約束條件下的最優(yōu)化問題。而在多人參與的博弈中，一個(gè)決策主體行為動(dòng)機(jī)還取決于其他決策者的行為。

一個(gè)博弈的基本要素包括參與者、行動(dòng)、信息、策略、支付和均衡。其中，信息是參與者在博弈中所掌握的全部知識(shí)，參與者的信息會(huì)隨時(shí)間的變化而改變;策略是參與者選擇行動(dòng)的規(guī)范，它指導(dǎo)參與者如何行動(dòng);支付是博弈中參與者的期望效用;均衡是所有參與者最優(yōu)策略的組合^[9]。

1.2 節(jié)點(diǎn)的理性偏好

由于本文所關(guān)注的是路徑的可靠度、網(wǎng)絡(luò)能耗和生存期，希望節(jié)點(diǎn)在合作選路的過程中能聯(lián)合優(yōu)化這三個(gè)性能。為實(shí)現(xiàn)這個(gè)目標(biāo)，每個(gè)節(jié)點(diǎn)的理性偏好必須與此一致。本文規(guī)定每個(gè)節(jié)點(diǎn)的理性偏好如下:

a）自己發(fā)送的數(shù)據(jù)能可靠地傳送到sink節(jié)點(diǎn)，這些數(shù)據(jù)包括節(jié)點(diǎn)本身產(chǎn)生的本地?cái)?shù)據(jù)和通過自己中轉(zhuǎn)的數(shù)據(jù)。

b)自己能活得久。這是為了避免某些位于關(guān)鍵位置(如從源節(jié)點(diǎn)到sink節(jié)點(diǎn)的最短路徑上)的節(jié)點(diǎn)由于頻繁地參與轉(zhuǎn)發(fā)數(shù)據(jù)而過度消耗自己的能量。這些節(jié)點(diǎn)過早的死亡會(huì)降低網(wǎng)絡(luò)的覆蓋率并縮短網(wǎng)絡(luò)的生存期^[9]。

1.3 博弈路由模型

基于以上節(jié)點(diǎn)的理性偏好，為了聯(lián)合優(yōu)化路徑的傳輸可靠度、網(wǎng)絡(luò)能耗和生存時(shí)間，本文給出了用擴(kuò)展式表述的博弈為這個(gè)動(dòng)態(tài)路由過程建模：

a）參與者集合。該博弈的參與者是網(wǎng)絡(luò)中任何一個(gè)存活的節(jié)點(diǎn)，設(shè)參與者的個(gè)數(shù)為n。b)參與者的行動(dòng)順序。該博弈由有本地?cái)?shù)據(jù)要傳的源節(jié)點(diǎn)發(fā)起，源節(jié)點(diǎn)先選擇一個(gè)合適的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，并向其發(fā)送路由請(qǐng)求，收到該路由請(qǐng)求的鄰居節(jié)點(diǎn)再開始采取相應(yīng)的行動(dòng)(如是否接收路由請(qǐng)求)。該決策過程一直持續(xù)到sink被選為下一跳節(jié)點(diǎn)為止。這個(gè)過程可以劃分為多個(gè)階段，第一個(gè)階段只有那些有本地?cái)?shù)據(jù)要傳的源節(jié)點(diǎn)行動(dòng)，其余階段由收到了路由請(qǐng)求的節(jié)點(diǎn)行動(dòng)。

c)參與者的行動(dòng)空間。包含兩類行動(dòng)，即不參與傳遞數(shù)據(jù)和參與傳遞數(shù)據(jù)并繼續(xù)向一個(gè)鄰居節(jié)點(diǎn)發(fā)送路由請(qǐng)求。源節(jié)點(diǎn)這類參與者的行動(dòng)空間只包含第二類行動(dòng)。令參與者i的第二類行動(dòng)用集合Li=(li1，…，lij，…，lim)，l(wèi)ij∈(0，1)來表示。其中：m表示參與者i可選的下一跳鄰居節(jié)點(diǎn)個(gè)數(shù)。為了避免路由環(huán)路，這m個(gè)鄰居節(jié)點(diǎn)不包括發(fā)送路由請(qǐng)求給i的那個(gè)節(jié)點(diǎn)。lij=1表示節(jié)點(diǎn)i選擇鄰居節(jié)點(diǎn)j作為下一跳節(jié)點(diǎn)，而lij=0表示節(jié)點(diǎn)i未選擇鄰居節(jié)點(diǎn)j作為下一跳節(jié)點(diǎn)。這里，僅考慮純策略空間的情況，此時(shí)，向量Li中最多只有一個(gè)值為1，其余都為0，即節(jié)點(diǎn)i只能選擇一個(gè)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。由于每個(gè)參與者的鄰居節(jié)點(diǎn)個(gè)數(shù)均有限，純策略空間的博弈中參與者的行動(dòng)空間是有限的。

d)參與者的信息集。這個(gè)信息集隨時(shí)間而變化。其中主要的信息包括參與者對(duì)鄰居節(jié)點(diǎn)和環(huán)境的知識(shí)，需要轉(zhuǎn)發(fā)的數(shù)據(jù)量，自己的剩余能量等。

e)參與者的支付函數(shù)(payoff)。博弈中參與者的每個(gè)行動(dòng)都會(huì)為該參與者帶來一定的效用，該效用由參與者效用支付函數(shù)來描述。由于博弈中參與者的策略和行動(dòng)均相互依賴，每個(gè)參與者的效用均與其他參與者策略有關(guān)。設(shè)博弈中任一組策略組合為s=(s1，s-i)。其中：si表示參與者i的策略；s-i=(s1，…，si-1，si+1，…，sn)表示其他參與者的策略。該策略組合下參與者i的payoff用Ui(si，s-i)來表示，其由i的收益Bi(si，s-i)和代價(jià)Ci(si，s-i)兩部分組成。

Bi(si，s-i)=Rup×Rij×Rj(1)

其中：Rup是從源節(jié)點(diǎn)到sink節(jié)點(diǎn)的傳輸可靠度；Rij是節(jié)點(diǎn)i與鄰居節(jié)點(diǎn)j之間傳輸可靠度；Rj是第j個(gè)鄰居節(jié)點(diǎn)到sink的傳輸可靠度。

Ci(si，s-i)=(Erxi+Etxi)×Fi/(LPi+LPj)（2）

其中：Erxi為節(jié)點(diǎn)i接收單位比特?cái)?shù)據(jù)的能耗；Etxi為節(jié)點(diǎn)i發(fā)送單位比特?cái)?shù)據(jù)的能耗；Fi為節(jié)點(diǎn)i中轉(zhuǎn)的數(shù)據(jù)量；LPi為節(jié)點(diǎn)i的剩余能量；LPj為節(jié)點(diǎn)j的剩余能量。根據(jù)式（1）（2）可得到一個(gè)聯(lián)合優(yōu)化傳輸可靠度、網(wǎng)絡(luò)的能耗與生存期的參與者payoff函數(shù)如下：

Ui(si，s-i)=Rup×Rij×Rj×(LPi+LPj)/[(Erxi+Etxi)×F] i參與傳遞數(shù)據(jù)

0其他（3）

2 UCEER路由協(xié)議

在無線傳感器網(wǎng)絡(luò)中，路由算法需要盡可能地保證單個(gè)節(jié)點(diǎn)與整個(gè)網(wǎng)絡(luò)同時(shí)得到能量優(yōu)化，從而延長網(wǎng)絡(luò)壽命，而兩者的優(yōu)化是相互依存又彼此矛盾的。單個(gè)節(jié)點(diǎn)的能量最優(yōu)化策略將減少節(jié)點(diǎn)之間的合作，增加節(jié)點(diǎn)直接與sink節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸?shù)拇螖?shù)，這對(duì)于網(wǎng)絡(luò)能量節(jié)省是十分不利的；而網(wǎng)絡(luò)能量最優(yōu)化策略可能由于過度使用某些熱點(diǎn)節(jié)點(diǎn)，而使這些熱點(diǎn)節(jié)點(diǎn)能量過早耗盡，從而影響網(wǎng)絡(luò)的整體傳輸性能。為了解決路由算法中整體與個(gè)體的矛盾，本文提出了新的路由算法——基于博弈論的無線傳感器網(wǎng)絡(luò)非均勻分簇節(jié)能路由算法UCEER。

圖1為UCEER路由協(xié)議的示意圖。其中，大小不等的圓表示簇首節(jié)點(diǎn)的大小非均勻的競爭范圍；帶箭頭的線表示簇首間的多跳數(shù)據(jù)傳輸。該路由協(xié)議利用非均勻的競爭半徑，使靠近sink節(jié)點(diǎn)的簇成員數(shù)目相對(duì)較小，從而簇首能夠節(jié)約能量以供數(shù)據(jù)轉(zhuǎn)發(fā)使用，達(dá)到均衡簇首能量消耗的目的。

根據(jù)第1章的無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)路由博弈模型，給出了具體的非均勻分簇節(jié)能路由的決策過程：

a）利用博弈思想建立網(wǎng)絡(luò)模型，包括參與者集合S；所有節(jié)點(diǎn)在某時(shí)刻的策略所構(gòu)成的策略集L，以及節(jié)點(diǎn)i成為簇首時(shí)的支付方程U。

b）每一個(gè)節(jié)點(diǎn)建立鄰節(jié)點(diǎn)信息集合，并廣播其U值。

c）接收到鄰節(jié)點(diǎn)U值的節(jié)點(diǎn)，將其與自身U值進(jìn)行比較，然后將大于自身U值的鄰節(jié)點(diǎn)記錄到鄰節(jié)點(diǎn)的信息集合中。

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

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

f）當(dāng)所有參與者均決定自身歸屬簇策略后，分層式路由建立，并開始數(shù)據(jù)傳輸。

由以上步驟可以看出，本算法中的均衡與傳統(tǒng)的納什均衡有所不同。首先本路由算法中的博弈為擴(kuò)展式博弈中的多階段可觀察行動(dòng)博弈，在整個(gè)過程中，博弈分階段進(jìn)行，所有參與人在某一階段選擇策略行動(dòng)時(shí)均知道所有相關(guān)參與人在以前階段所選擇的行動(dòng)；其次所有參與者在選擇行動(dòng)時(shí)均根據(jù)所有相關(guān)參與人的歷史行動(dòng)策略以及相關(guān)信息作出策略選擇；再次該多階段博弈的策略組合在每一個(gè)階段均為納什均衡；而最終策略組合為完美子博弈均衡。

3 仿真結(jié)果與分析

為了檢驗(yàn)UCEER的性能，本文使用NS2網(wǎng)絡(luò)仿真器分別對(duì)UCEER、LEACH協(xié)議進(jìn)行仿真，通過仿真結(jié)果比較其性能。主要仿真參數(shù)設(shè)置如表1所示。

為簡單起見，假設(shè)采用理想的MAC協(xié)議，忽略無線鏈路中可能發(fā)生的丟包錯(cuò)誤。實(shí)驗(yàn)中統(tǒng)計(jì)傳感器節(jié)點(diǎn)接收數(shù)據(jù)、融合數(shù)據(jù)和發(fā)送數(shù)據(jù)所消耗的能量，計(jì)算網(wǎng)絡(luò)的存活時(shí)間（用輪數(shù)表示），來分析協(xié)議的能量效率。

筆者從實(shí)驗(yàn)中隨機(jī)選取10輪，統(tǒng)計(jì)各輪中所有簇首消耗的能量之和，結(jié)果如圖2所示。從圖中可以看出，UCEER的簇首消耗的能量遠(yuǎn)小于LEACH的簇首所耗能量。LEACH的簇首能耗之和之所以較高，是因?yàn)長EACH的簇首采用單跳的方式發(fā)送數(shù)據(jù)到sink節(jié)點(diǎn)，且LEACH沒有控制簇首在網(wǎng)絡(luò)中的分布，因此簇首能耗之和有明顯的波動(dòng)。而在UCEER中顯著地降低了能耗，是因?yàn)槠洳捎貌┺睦碚摽刂撇呗允沟么厥追植驾^為合理，使得每一輪簇首能耗之和變化較小，有利于延長網(wǎng)絡(luò)壽命。

圖3顯示了UCEER和LEACH兩種算法的網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)隨時(shí)間變化的情況。從圖中可以看出，無論是第一個(gè)節(jié)點(diǎn)死亡的時(shí)間還是最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間，UCEER算法均優(yōu)于LEACH，可見其有效地延長了無線傳感器網(wǎng)絡(luò)的壽命。且UCEER中從第一個(gè)節(jié)點(diǎn)死亡到最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間跨度很小，這說明在UCEER路由協(xié)議中引入博弈理論來控制簇首分布的策略較好地均衡了網(wǎng)絡(luò)節(jié)點(diǎn)能耗，從而高效地利用了網(wǎng)絡(luò)中有限的能量，延長了網(wǎng)絡(luò)生存期。

4 結(jié)束語

目前傳感器網(wǎng)絡(luò)仍存在很多相關(guān)技術(shù)問題值得研究。其中，路由技術(shù)特別是以降低能耗為目標(biāo)的節(jié)能路由技術(shù)是無線傳感網(wǎng)絡(luò)設(shè)計(jì)的關(guān)鍵之一。

本文提出了一種基于博弈論的無線傳感器網(wǎng)絡(luò)非均勻分簇節(jié)能路由算法：通過對(duì)LEACH算法的分析可以看出，它是一種比較高效節(jié)能的網(wǎng)絡(luò)分簇算法，其不足之處在于它隨機(jī)選舉簇首的方式破壞了網(wǎng)絡(luò)的負(fù)載均衡性，導(dǎo)致網(wǎng)絡(luò)壽命的縮短和傳輸吞吐量的降低；而通過本文的基于博弈論的非均勻分簇策略，解決了節(jié)點(diǎn)能耗分布不均的難題。該算法體現(xiàn)出了其自適應(yīng)調(diào)整簇首、調(diào)節(jié)節(jié)點(diǎn)負(fù)荷、延長網(wǎng)絡(luò)平均壽命的能力。通過仿真結(jié)果分析，可以看出該算法具有如下特點(diǎn)：

a）算法是完全分布式的；

b）算法能夠提高全網(wǎng)的數(shù)據(jù)傳輸吞吐量；

c）算法能夠達(dá)到時(shí)間同步的要求。

經(jīng)分析和仿真驗(yàn)證，本文算法比LEACH算法減少了近40%的能量消耗。

參考文獻(xiàn)：

［1］鄭少仁，王海濤，趙志峰，等.Ad hoc網(wǎng)絡(luò)技術(shù)[M].北京:人民郵電出版社，2005.

[2]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[3]任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，2003，14(7):12821291.

[4]KANNAN R，RAY L，KALIDINDI R，et al.Maxmin lengthenergyconstrained routing in wireless sensor networks[C]//Proc of the 1st European Conference on Wireless Sensor Networks.Berlin:Springer，2004:234249.

[5]KANNAN R，IYENGAR S.Gametheoretic models for reliable pathlength and energyconstrained routing with data aggregation in wireless sensor networks[J].IEEE Trans on Selected Areas of Communications，2004，22(6):11411150.

[6]WANG Weidong，ZHU Qingxin.A hierarchical clustering algorithm and cooperation analysis for wireless sensor networks[J].Journal of Software，2006，17(5):11571167.

[7]MANJESHWAR A，AGARWAL D P.TEEN:a routing protocol for enhanced efficiency in wireless sensor networks[C]//Proc of the 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing.San Francisco:IEEE Computer Society，2001:20092015.

[8]LI Chengfa，YE Mao，CHEN Guihai，et al.An energyefficient unequal clustering mechanism for wireless sensor networks[C]//Proc of the 2nd IEEE International Conference on Mobile Ad hoc and Sensor Systems(MASS 2005).Washington DC:[s.n.]，2005:597-604.

[9]李慧芳，姜?jiǎng)倜鳎f崗.無線傳感器網(wǎng)絡(luò)中基于博弈論的路由建模[J].傳感技術(shù)學(xué)報(bào)，2007，20(9)：20752080.

[10] REISFELD D，WOLFSON H，YESHURUN Y.Context free attentional operators: the generalized symmetry transforms [J].International Journal of Computer Vision，1995，14(2):119130.

[11]REISFELD D YESHURUN Y.Preprocessing of face images: detection of features and pose normalization[J].Computer Vision and Image Understanding，1998，71(3):413-430.