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

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

0 引 言

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

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

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

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

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

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

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

2.1 博弈論介紹

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

現(xiàn)代博弈論可分為合作博弈和非合作博弈。合作博弈是研究人們達(dá)成合作時(shí)如何分配合作所得收益，即收益分配問題［7］;非合作博弈是研究人們?cè)诶嫦嗷ビ绊懢謩?shì)下如何決策使自身收益最大，即策略選擇問題［6～8］。博弈可用三要素表示

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

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

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

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

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

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

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

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

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

2)參與者與策略空間

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

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

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

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

［8］給出了定理1 及其證明過程，而定位博弈納什平衡點(diǎn)存在性分兩點(diǎn)來證明: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情況下，對(duì)收益函數(shù)(式(3))求二階導(dǎo)數(shù)

綜合考慮兩項(xiàng)因素，此博弈存在納什平衡點(diǎn)。

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

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

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

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

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

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

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

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

4 仿真與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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

參考文獻(xiàn):

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

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

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

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

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

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

［7］ 黃 河.各向異性無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位問題研究［D］.合肥:中國(guó)科技大學(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é)點(diǎn)定位技術(shù)［J］.計(jì)算機(jī)工程，2010，36(10):85－87.

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