大規(guī)模帶狀無線傳感器網(wǎng)絡(luò)節(jié)點定位算法*

魯銀芝，仲元昌，楊 柳，李發(fā)傳

(重慶大學(xué) 通信工程學(xué)院，重慶400044)

0 引 言

長江三峽工程是舉世矚目的特大型水利工程，在其帶來巨大經(jīng)濟、社會效益的同時，庫區(qū)面臨著嚴(yán)峻生態(tài)環(huán)境安全問題［1～3］，迫切需要建立高效的庫區(qū)水環(huán)境實時監(jiān)測系統(tǒng)，以實現(xiàn)水質(zhì)狀況監(jiān)測和水域突發(fā)事件應(yīng)急處理［4］?，F(xiàn)有監(jiān)測設(shè)備和方法已不能滿足現(xiàn)實需求，必須要加強環(huán)境監(jiān)測能力并提高監(jiān)測水平［5，6］。無線傳感器網(wǎng)絡(luò)(WSNs)適用于環(huán)境惡劣、人類不便到達(dá)和需要長期監(jiān)測的廣闊區(qū)域［5～7］。在三峽庫區(qū)水環(huán)境監(jiān)測系統(tǒng)中引入無線傳感器網(wǎng)絡(luò)，能夠克服傳統(tǒng)監(jiān)測方式的限制多、反應(yīng)慢、無法實時連續(xù)監(jiān)測等缺點［6］。

節(jié)點定位是無線傳感器網(wǎng)絡(luò)支撐技術(shù)之一，水環(huán)境監(jiān)測過程中，采集的數(shù)據(jù)須包含位置信息，以便分析具體地理區(qū)域下水環(huán)境信息和處理突發(fā)性應(yīng)急事件，降低風(fēng)險［1～3］。因項目需要，在已有定位算法的基礎(chǔ)上，結(jié)合應(yīng)用網(wǎng)絡(luò)特點［4，5］，本文提出了一種大規(guī)模帶狀無線傳感器網(wǎng)絡(luò)節(jié)點定位算法。

1 大規(guī)模帶狀無線傳感器網(wǎng)絡(luò)特性

三峽庫區(qū)是在長江三峽這個特殊的區(qū)域，如圖1，庫區(qū)呈現(xiàn)蜿蜒的樹狀結(jié)構(gòu)，具有明顯的帶狀特征，且分布范圍廣［2］。面向三峽庫區(qū)水環(huán)境監(jiān)測的大規(guī)模無線傳感器網(wǎng)絡(luò)應(yīng)根據(jù)其特性部署、組網(wǎng)。宏觀上，這是一種超大規(guī)模復(fù)雜無線帶狀網(wǎng);微觀上，可將其分解成多個小型帶狀子網(wǎng)［5］。帶狀分布傳感器網(wǎng)絡(luò)具有自身特性［4～6］，節(jié)點定位過程中應(yīng)深入分析其特點，采用合適定位算法才能取得良好效果。

圖1 三峽庫區(qū)水域分布圖Fig 1 Distribution of the Three Gorges Reservoir

博弈論作為數(shù)學(xué)建模分析工具已被廣泛采用［7］，但很少有學(xué)者將節(jié)點定位問題與博弈論建模結(jié)合分析［8］。本文結(jié)合三峽庫區(qū)水環(huán)境監(jiān)測的傳感器網(wǎng)絡(luò)特性，著重將博弈論用于未知節(jié)點的定位并進(jìn)行模型搭建，尋找合適方法對模型求解，改善定位算法性能。

2 無線傳感器網(wǎng)絡(luò)節(jié)點定位模型

2.1 博弈論介紹

博弈論作為研究決策主體之間行為發(fā)生直接相互作用時的建模和決策均衡問題的手段，早在十幾年前已被提出［7］。近年來，博弈論思想逐漸用于無線傳感器網(wǎng)絡(luò)的研究領(lǐng)域，為諸如路由、拓?fù)淇刂萍百Y源分配［8］等關(guān)鍵技術(shù)帶來新思路。

現(xiàn)代博弈論可分為合作博弈和非合作博弈。合作博弈是研究人們達(dá)成合作時如何分配合作所得收益，即收益分配問題［7］;非合作博弈是研究人們在利益相互影響局勢下如何決策使自身收益最大，即策略選擇問題［6～8］。博弈可用三要素表示

式中 N 為博弈參與人集合，S 為參與人可選策略集合，U為在給定策略S 情況下參與人的收益［8］。

2.2 基于博弈論定位算法模型

為實現(xiàn)高精度節(jié)點定位，定位過程包括初始定位階段和求精階段。若未知節(jié)點存在鄰居錨節(jié)點或2 跳錨節(jié)點［9，10］，在錨節(jié)點覆蓋區(qū)域的交集取一定數(shù)量點，將點坐標(biāo)平均值作為該未知節(jié)點的初始坐標(biāo)。

定位求精階段，節(jié)點多次重復(fù)或迭代定位［10，11］。所有節(jié)點參與博弈，構(gòu)建非合作博弈［8］模型。錨節(jié)點自身位置已知，即已有最優(yōu)策略，無須再調(diào)整;未知節(jié)點不斷調(diào)整策略使自身收益更高。博弈結(jié)束后進(jìn)入平衡狀態(tài)，即單個節(jié)點獨自改變策略并不能增加自身收益。

1)收益函數(shù)構(gòu)造

設(shè)(exi，eyi)，(exj，eyj)為節(jié)點i，j 的估計坐標(biāo)，lij為估計坐標(biāo)間距離，dij為實際測定距離，εij為lij與dij的差值，則有

若節(jié)點i，j 的估計坐標(biāo)與實際坐標(biāo)接近，則意味著εij很小，定位更精確。構(gòu)造函數(shù)

當(dāng)式(3)累加項的第二項最小，即εij為零時，函數(shù)取最大值，如式(4)

此時節(jié)點定位結(jié)果與真實情況一致。

2)參與者與策略空間

基于定位的博弈模型中，參與者是所有節(jié)點的集合，用N={1，…，m}表示。設(shè)Xi表示第i 個參與者的策略集，即節(jié)點i 可選估計坐標(biāo)點的集合。記^i=N/i，即^i 表示參與者集合中除i 以外的其他參與者集合［9］，如下式集值映射關(guān)系

式中 X 為局中所有策略空間集合，ui為參與者i 的收益函數(shù)。

3)基于博弈論定位模型的納什平衡點

定理1 對參與者集合N 中任意參與者i，設(shè)其策略空間集Xi是Hausdorff 局部凸空間Ei中的非空凸緊集，ui∶X→R連續(xù)，且任意x^i屬于)在Xi上擬凹連續(xù)，則此博弈的納什平衡點存在［7，8］。

［8］給出了定理1 及其證明過程，而定位博弈納什平衡點存在性分兩點來證明:1)X 是Rn中的非空凸緊集［7］;2)ui∶X→R 連續(xù)，xi→ui(xi，x^i)在Xi上擬凹連續(xù)［8］。證明過程如下:

1)X 中所有策略的取值都是在一定限制區(qū)域內(nèi)可連續(xù)的，所以，X 是Rn中的非空凸緊集。

2)收益函數(shù)xi→ui(xi，x^i)在Xi上擬凹連續(xù)的判定只需證明函數(shù)可微。參與者i 在選擇策略xi情況下，對收益函數(shù)(式(3))求二階導(dǎo)數(shù)

綜合考慮兩項因素，此博弈存在納什平衡點。

3 基于博弈論的定位算法實現(xiàn)

假設(shè)參與者節(jié)點都是理性的，均追求收益最大化，定位過程步驟如下［12，13］:

1)在指定二維區(qū)域隨機部署N 個未知節(jié)點和M 個錨節(jié)點。部署完成后節(jié)點開始相互通信，通信半徑為R。

2)錨節(jié)點廣播自身的位置信息數(shù)據(jù)報，其鄰居節(jié)點接收并轉(zhuǎn)發(fā)，數(shù)據(jù)報只轉(zhuǎn)發(fā)一次。

3)未知節(jié)點收集兩個錨節(jié)點的坐標(biāo)信息(沒有一跳錨節(jié)點才使用兩跳錨節(jié)點信息)。

4)初始化未知節(jié)點坐標(biāo)。若未知節(jié)點收集到兩個錨節(jié)點的數(shù)據(jù)，則以兩個錨節(jié)點的坐標(biāo)為圓心，到未知節(jié)點距離的1.25 倍為半徑畫圓，如圖2，在兩圓的交區(qū)域取p 個點，坐標(biāo)取平均值后作為未知節(jié)點的初始坐標(biāo);否則，等待下一輪定位。

圖2 采樣區(qū)域示意Fig 2 Sampling area illustration

5)采用基于博弈論的定位算法對初始化后的節(jié)點進(jìn)行優(yōu)化求精，如下偽程序:

4 仿真與分析

為分析算法性能，利用Matlab 7.1 進(jìn)行仿真實驗。

網(wǎng)絡(luò)平均定位誤差定義如下

式中 n 為網(wǎng)絡(luò)中未知節(jié)點個數(shù);v 為網(wǎng)絡(luò)標(biāo)號;i 為第i 個未知節(jié)點;x'i為節(jié)點i 的估計坐標(biāo)矩陣;xi為節(jié)點i 的實際坐標(biāo)矩陣;Rv為節(jié)點的通信半徑;Ev為網(wǎng)絡(luò)v 的平均定位誤差。

規(guī)定150 m×150 m 的矩形為仿真區(qū)域，隨機部署100 個未知節(jié)點和30 個錨節(jié)點。如圖3，節(jié)點通信半徑為30 m，空心圓點表示未知節(jié)點實際位置，星號表示未知節(jié)點估計位置，實心三角號表示錨節(jié)點位置。圖3(a)為初始化后節(jié)點定位結(jié)果，誤差率高達(dá)54.78%;圖3(b)為優(yōu)化后的節(jié)點最終定位結(jié)果，誤差率僅為7.17%，網(wǎng)絡(luò)邊緣未知節(jié)點因連通度比中心未知節(jié)點低，定位精度稍有降低，但總體效果良好。

圖3 正方形分布節(jié)點定位結(jié)果Fig 3 Localization result of nodes distribution in square area

在140 m×500 m 的矩形區(qū)域中傳感器節(jié)點呈帶狀分布，節(jié)點密度、錨節(jié)點比例和節(jié)點通信半徑與圖3 相同。圖4(a)為初始化后節(jié)點定位結(jié)果。圖4(b)為優(yōu)化后的節(jié)點最終定位結(jié)果。

在100 m×500 m 的矩形區(qū)域中使傳感器節(jié)點呈條形分布，節(jié)點密度、錨節(jié)點比例以及節(jié)點通信半徑與圖3 相同。圖5(a)為初始化后節(jié)點定位結(jié)果，圖5(b)為優(yōu)化后的節(jié)點最終定位結(jié)果。

為分析通信半徑對定位精度和節(jié)點定位覆蓋率的影響，在通信半徑由小到大變化時，觀察定位情況。隨機試驗20 次求節(jié)點定位誤差和覆蓋率平均值。

圖6 表示節(jié)點定位覆蓋率隨通信半徑R 的變化情況，R越大，節(jié)點覆蓋率越高。當(dāng)節(jié)點通信半徑增大時，網(wǎng)絡(luò)連通度增加，鄰居節(jié)點增多，有利于提高節(jié)點定位覆蓋率。

圖7 表示節(jié)點定位誤差隨通信半徑R 的變化情況，R增大時，定位誤差降低。通信半徑越大，與待定位節(jié)點直接通信的未知節(jié)點和錨節(jié)點數(shù)目增加。在與周圍節(jié)點進(jìn)行博弈過程中，更易于找到最優(yōu)策略。

圖4 帶狀分布節(jié)點定位結(jié)果Fig 4 Localization result of nodes in zonal distribution

圖5 條形分布節(jié)點定位結(jié)果Fig 5 Localization result of nodes in strip distribution

圖6 節(jié)點定位覆蓋率隨通信半徑變化Fig 6 Change of node localization coverage rate with communication radius

5 結(jié) 論

本文針對基于三峽庫區(qū)水環(huán)境監(jiān)測的大規(guī)模帶狀無線傳感器網(wǎng)絡(luò)，將博弈理論和優(yōu)化算法應(yīng)用于節(jié)點定位問題，建立節(jié)點定位優(yōu)化算法模型。結(jié)合三峽庫區(qū)特點，對不同區(qū)域形狀分布下的網(wǎng)絡(luò)進(jìn)行定位仿真實驗。實驗結(jié)果表明了算法的可行性和高效性，在不增加硬件開銷的情況下提高了定位精度和節(jié)點覆蓋率。

圖7 節(jié)點定位誤差隨通信半徑變化Fig 7 Change of node localization error with communication radius

參考文獻(xiàn):

［1］ 畢海普.三峽庫區(qū)突發(fā)水污染事故的數(shù)值模擬及風(fēng)險評估研究［D］.重慶:重慶大學(xué)，2011.

［2］ 季富政.長江三峽地區(qū)概貌［J］.重慶建筑，2010(9):1－7.

［3］ 劉玉邦，梁 川.長江上游水資源保護分區(qū)研究［J］.中國農(nóng)村水利水電，2009(4):10－14.

［4］ 劉昊靈，仲元昌，楊 柳，等.基于三峽庫區(qū)水環(huán)境監(jiān)測的WSNs 信息融合算法［J］.傳感技術(shù)學(xué)報，2012，25(12):1761－1765.

［5］ 仲元昌，宋 揚.大規(guī)模無線傳感器網(wǎng)絡(luò)自適應(yīng)節(jié)能路由算法［J］.計算機工程與應(yīng)用，2013，49(1):89－93.

［6］ 康 晶.基于博弈論的無線傳感器網(wǎng)絡(luò)節(jié)點間通信的研究［EB/OL］.北京:中國科技論文在線.［2011—01—12］.http:∥www.paper.edu.cn/releasepaper/content/201101－557.

［7］ 黃 河.各向異性無線傳感網(wǎng)絡(luò)節(jié)點定位問題研究［D］.合肥:中國科技大學(xué)，2011.

［8］ 俞 建.博弈論與非線性分析［M］.北京:科學(xué)出版社，2008:74－113.

［9］ Kulkarni R V，Venayagamoorthy G K，Cheng M X.Bio－inspired node localization in wireless sensor networks［C］∥IEEE International Conference on Systems，Man and Cybernetics，SMC 2009，IEEE，2009:205－210.

［10］Sivakumar S，Venkatesan R，Karthiga M.Error minimization in localization of wireless sensor networks using genetic algorithm［J］.International Journal of Computer Applications，2012，43(12):16－20.

［11］Niewiadomska－Szynkiewicz E.Localization in wireless sensor networks:Classification and evaluation of techniques［J］.International Journal of Applied Mathematics and Computer Science，2012，22(2):281－297.

［12］章 磊，段莉莉，錢紫鵑，等.基于遺傳算法的WSNs 節(jié)點定位技術(shù)［J］.計算機工程，2010，36(10):85－87.

［13］馬 震，劉 云，沈 波.分布式無線傳感器網(wǎng)絡(luò)定位算法MDS—MAP(D)［J］.通信學(xué)報，2008，29(6):57－62.