王 明,孟 赟,李 競,應可珍,陳慶章

(1.寧波大紅鷹學院信息工程學院,浙江 寧波 315175;2.杭州華三通信技術有限公司,杭州 310053;3.浙江工業(yè)大學計算機學院,杭州 310023;4.浙江財經大學東方學院,浙江 海寧 314408)

?

用于無線傳感器網絡的節(jié)點間協(xié)同定位算法的設計*

王 明1,孟 赟1,李 競2,應可珍3,4,陳慶章3*

(1.寧波大紅鷹學院信息工程學院,浙江 寧波 315175;2.杭州華三通信技術有限公司,杭州 310053;3.浙江工業(yè)大學計算機學院,杭州 310023;4.浙江財經大學東方學院,浙江 海寧 314408)

給出一種無線傳感器網絡中無錨節(jié)點情況下的節(jié)點間相互協(xié)同定位的算法。它首先將節(jié)點進行分簇,把角度測量和距離測量結合起來,通過方位協(xié)同,逐步對同步中的節(jié)點進行方位調整和坐標調整,從而計算出所有節(jié)點的相對坐標。仿真結果表明,在節(jié)點隨機分布的情況下,該算法比起業(yè)界公認的聚類SPA算法在網絡覆蓋率、定位誤差率和通信開銷3個方面都有更好的表現。

無線傳感器網絡;協(xié)同定位算法;無錨節(jié)點定位;節(jié)點分簇

無線傳感器網絡WSN(Wireless Sensor Network)是大量的靜止或移動的傳感器以自組織和多跳的方式構成的無線網絡,目的是協(xié)作地探測、處理和傳輸網絡覆蓋區(qū)域內感知對象的監(jiān)測信息,并報告給用戶。無線傳感器網絡被列為2l世紀最有影響的21項技術和改變世界的10大技術之一[1-2]。網絡中的節(jié)點通常被隨機布置在不同的環(huán)境中以實現各種監(jiān)測工作,監(jiān)測數據有效性與節(jié)點所處位置密切相關。因此,用以確定節(jié)點位置的節(jié)點定位技術是無線傳感器網絡研究的重點之一。

目前常見的節(jié)點定位方法是在所布屬的節(jié)點中,設置部分具有全球衛(wèi)星定位系統(tǒng)GPS(Global Positioning System)功能的節(jié)點,我們稱之為錨節(jié)點(beacon node),其他節(jié)點的位置則根據錨節(jié)點來進行計算。但實際應用中,因為各種原因常常無法設置錨節(jié)點,此時的節(jié)點定位就必須實現節(jié)點之間協(xié)同工作的相對定位,也稱節(jié)點自定位或節(jié)點協(xié)同定位。這種無錨節(jié)點的協(xié)同定位算法,其原理是通過無線傳感網絡內部節(jié)點間的相互測距和信息交換,得出節(jié)點的相對位置。此類算法雖然無法與基于錨節(jié)點定位算法一樣可以測出節(jié)點的絕對位置信息,其所得到的相對位置信息足可以應用在對象監(jiān)測、同步、尤其是基于地理位置的路由(geo-routing)[3]等應用上。并且如果以后能夠取得3組以上的實體坐標系位置信息時,便可輕易將該相對坐標系統(tǒng)轉換為絕對坐標系統(tǒng),增進了使用上的彈性與便利性。

本文提出的無錨節(jié)點的協(xié)同定位算法,結合了角度測量和距離測量,通過方位協(xié)同逐步對同步中的節(jié)點進行方位調整,從而計算出所有節(jié)點在區(qū)域坐標系統(tǒng)當中的坐標。

1 相關研究

目前關于無錨節(jié)點定位算法的研究得到了高度重視,并推出很多研究成果。Motomura S等提出的無錨節(jié)點的定位方法,它只需要局部傳感器節(jié)點的協(xié)同交互來確定傳感器節(jié)點的位置,該方法利用鏈路質量指示器LQI(Link Quality Indicator)和節(jié)點間的跳數進行測量[4]。Chen Yuan-Fang等提出了一種不需要依賴GPS支持的錨節(jié)點的室內定位算法,該算法利用一個移動節(jié)點,使其在部署區(qū)域內沿著特定的軌跡移動并根據起始坐標和移動信息計算實時坐標[5]。傅賢鋒等引入錨節(jié)點定位算法中共線度的概念,提出一種基于超聲波四元陣測距的無錨節(jié)點定位算法[6]。Emokpae L等介紹了一種基于表面的反射模型,利用同態(tài)反褶積技術建立水表面反射通信鏈路,在此基礎上建立一種可以用于獨立節(jié)點建立相對坐標系的基于表面的反射無錨節(jié)點定位算法[7]。此外,也有結合兩者優(yōu)點開展的研究,如利用多維標度技術MDS(Multidimensional Scaling),采用少量錨節(jié)點實現網絡定位的MDS-MAP算法[8],并且劉健苗等在此基礎上引入Euclidean距離估算思想構建距離矩陣,并優(yōu)化了最小二乘逼近的坐標轉換方法對MDS-MAP算法進行了改進,獲得了較好的效果[9]。

分析已經推出的研究成果,比較典型的無錨節(jié)點定位算法還是SPA(Self-Positioning Algorithm)[10]、聚類SPA[11]和MAP-Growing[12]3種。在SPA算法中,網絡中每一個節(jié)點首先選取兩個鄰居節(jié)點建立該節(jié)點自身的坐標系統(tǒng)與坐標軸方向,再利用三邊定位法,向外推算出其他節(jié)點的對應位置。再利用此方法構建其他節(jié)點的坐標系。之后再選定其中一個或一群節(jié)點作為坐標原點,通過節(jié)點合并建立一個整體的坐標系。在此算法中,由于每個節(jié)點都需要參與多次的坐標轉換,算法的通信開銷非常大。由于此算法針對無線自組織網絡提出的,不需考慮能耗情況,若移植到無線傳感器網絡中,這種算法便不適合。為了提高上述SPA算法的擴展性,以及改進通信量過大的問題,Iyengar R等提出了聚類SPA算法。此算法首次引入了聚類思想,加入了分簇階段,使算法整體的時間、通信開銷減少,但存在后期冗余通信多、網絡覆蓋率不高的問題。Map-Growing算法是一種基于測距的算法,由Missouri-Columbia大學的Xiaoli Li等提出。其基本思想是構建3個內角都大于30°的良好三角形,并采用遞歸算法,重復地進行三邊定位,從而獲取節(jié)點坐標,最后再轉換為全局絕對坐標。該算法實現簡單、拓撲結構要求低,但存在累計誤差現象,算法收斂速度慢。

針對以上現狀,本文在SPA算法的基礎上,提出了無錨節(jié)點的協(xié)同定位算法即CCPA算法(Clustering-based and Collaborative Positioning Algorithm In Anchor-free),該算法對節(jié)點進行聚類分簇。與Iyengar r等人提出的聚類SPA算法相比,CCPA算法在性能上將得到明顯的提升。

2 無錨節(jié)點的協(xié)同式定位算法設計

2.1 算法思想

與聚類SPA算法類似,CCPA算法也分為分簇、建立局部坐標和建立全局坐標3個階段。但聚類SPA算法存在分簇不均勻、簇間交集大、部分節(jié)點無法找到合適的鄰居節(jié)點計算坐標以及因邊界節(jié)點不足無法轉換到全局坐標等問題。為了解決這些不足,CCPA算法在分簇和定位方面采取了不同的方式:

①簇形成階段:先將網絡初始化,在基于節(jié)點密度的分簇算法CAND(Clustering Algorithm based on Node Density)[13-14]的基礎上,使用改進后的基于節(jié)點密度的分簇算法ICAND(Improved CAND)進行分簇,選出主節(jié)點,以主節(jié)點為中心的周圍一跳鄰居為從節(jié)點,將整個網絡分為帶有交叉區(qū)域的各個簇,把各節(jié)點分成3類:主節(jié)點、從節(jié)點和邊界節(jié)點。其中邊界節(jié)點定義為從屬于i節(jié)點簇(甚至可能是主節(jié)點i自身)同時能收聽到其他簇節(jié)點(主節(jié)點或從節(jié)點都行)的節(jié)點,而聚類SPA算法將邊界節(jié)點定義為從屬于i節(jié)點簇同時又能收聽到其他簇的主節(jié)點的節(jié)點,相比而言本算法對邊界節(jié)點的定義更寬泛。

②簇內同步階段:節(jié)點通過多個超聲波接收機或天線陣列感知發(fā)射節(jié)點信號的到達方向,從而測得對應的相對方位或角度,利用角度測量數據實現簇內節(jié)點的方位同步。方向是從節(jié)點同步到主節(jié)點,主節(jié)點依此以自身為坐標原點建立局部坐標系,通過上個階段所得的角度和距離信息,利用本文推導出的公式計算出各從節(jié)點在所屬局部坐標系的坐標值。

③全局協(xié)同階段:首先是與全局中心簇相鄰的簇的主節(jié)點通過與邊界節(jié)點交換數據包,在此僅需一個邊界節(jié)點即可完成兩簇間的合并,計算出本局部坐標系同步到全局坐標系的相應信息,先實現全局節(jié)點的方位同步,再實現距離同步,同步至全局坐標系;與已同步簇相鄰的簇同樣依此方法同步到全局坐標系,如此重復以全局簇為中心向外同步,直至所有簇都同步到全局坐標系,從而實現節(jié)點的自定位。

為了獲得節(jié)點間的距離信息以及建立坐標系,CCPA算法使用了5種不同的消息類型來進行節(jié)點內部通信。每個消息類型包括發(fā)送端節(jié)點ID(NodeID)、主節(jié)點ID(MasterID)、消息類型、消息體(Body)4部分內容。5種消息類型的組成如下:

①DISTANCE[NodeID,MasterID,Distance,Body]:讓鄰居節(jié)點獲得與發(fā)送節(jié)點之間的距離信息。在基于測距的定位中,需要測得相鄰節(jié)點間的距離或角度,目前的主流技術包括RSSI、AOA、TOA、TAOA等[15]。其中的TOA(Time of Arrival)[16]算法根據到達時間來實現節(jié)點間距離的測算,其具有成本低的優(yōu)點。本算法采用TOA方法來測距,因而Body中的內容是發(fā)送節(jié)點在發(fā)送本消息時的時間戳。

②ANGLESYNC[NodeID,MasterID,AngleSync,Body]:本消息用于簇內同步階段的角度同步,Body包含的是同步的輪次和主節(jié)點測量出從節(jié)點相對于自身坐標所在的角度值。

③CENTER[NodeID,MasterID,Center,Body]:本消息用于全局協(xié)同階段。用來選取全局坐標系統(tǒng)的原點,Body中包含的是主節(jié)點的連通度。

④BORDER[NodeID,MasterID,Border,Body]:本消息用于全局協(xié)同階段。由邊界節(jié)點發(fā)送給鄰居簇的主節(jié)點或從節(jié)點。Body中包括數組{nodeID,Angle,coordinates1,coordinates2}。nodeID是鄰居節(jié)點的ID號,Angle是此邊界節(jié)點測量得相對于nodeID節(jié)點的相對方向角,coordinates1是此邊界節(jié)點在主簇的局部坐標值,coordinates2是此邊界節(jié)點在以nodeID節(jié)點為坐標原點的坐標系中的局部坐標值。

⑤MERGE[NodeID,MasterID,Merge,Body]:本消息用于全局協(xié)同階段。Body中包括的是需逆時針調整的角度和發(fā)送節(jié)點在全局坐標系中的坐標值。

2.2 簇形成

高效的分簇算法是提高定位算法效率的關鍵。這里采用的ICAND算法通過降低簇與簇之間的重疊度和對生成簇大小的限制來提高分簇效率。具體分為4階段:

①網絡初始化階段。節(jié)點廣播自身ID、當前獲得的鄰居節(jié)點的數目和ID。鄰居節(jié)點收到消息后,更新自己的鄰節(jié)點信息表,里面儲存著所有的一跳鄰節(jié)點的ID、此節(jié)點到本節(jié)點的距離、其鄰節(jié)點數目、所入簇的數量以及所屬簇ID列表共5項,并根據其鄰節(jié)點數目的大小通過選擇排序算法進行排序。

②成簇階段。各節(jié)點設置一個隨機定時器,時間一到,便比較自己和所有的一跳鄰居節(jié)點的連通度,具有最大連通度的那個節(jié)點被選取為主節(jié)點。然后,當選的主節(jié)點判斷自己的連通度是否大于網絡預先設定的閾值T。連通度如果大于T,則搜索自身鄰節(jié)點信息表中T個擁有最少鄰節(jié)點數目的節(jié)點發(fā)布RECRUIT消息,否則,廣播RECRUIT消息給鄰節(jié)點信息表中的所有節(jié)點。收到RECRUIT消息的節(jié)點入簇,記錄下主節(jié)點ID號,成為從節(jié)點,如果已經入別的簇,同樣入該簇,成為邊界節(jié)點。通知鄰居節(jié)點,并更新自己的鄰節(jié)點信息表。在此處,已選擇了主節(jié)點的節(jié)點稱為“covered node”,不再參與主節(jié)點的選取。還未選擇主節(jié)點的節(jié)點稱為“uncovered node”。

③遷移階段。主節(jié)點計算本簇的冗余度,即邊界節(jié)點的數目與簇內節(jié)點總數的比值。令冗余度閾值為50%。如果冗余度超過閾值,則主節(jié)點準備遷移。主節(jié)點從鄰節(jié)點信息表中選取密度即連通度最大的從節(jié)點作為候選節(jié)點,把主節(jié)點的位置讓賢給此候選節(jié)點。首先通知鄰居節(jié)點自己成為了普通節(jié)點,而候選節(jié)點成為了新的主節(jié)點。收到此消息的節(jié)點,如果為候選節(jié)點,則改變自身的狀態(tài)為簇頭,發(fā)布RECRUIT消息;如果為舊主節(jié)點與新主節(jié)點的公共節(jié)點,則更新鄰節(jié)點信息表,更換所屬主節(jié)點的ID;如果為舊主節(jié)點成員而非新主節(jié)點的鄰居,則更新鄰節(jié)點信息表,把自身狀態(tài)改為“uncovered”,完成簇的遷移階段。

④結束階段。當前兩個階段結束以后,可能有少量節(jié)點還在“uncovered”狀態(tài),所以最后需要再進行一次“clean-up”即清理過程,該過程不再進行簇的遷移,其自舉成為簇頭,發(fā)布RECRUIT消息,這樣可以保證每個節(jié)點都屬于一個簇或多個簇。至此整個ICAND算法結束。

2.3 簇內協(xié)同

簇內協(xié)同是指簇內的方位協(xié)同,通過調整簇內從節(jié)點的坐標軸方位來實現。在初始條件下,由于節(jié)點的隨機部署,每個節(jié)點都有一個自身認知的Y軸正方位(正北方向),并以自身為坐標原點自行定義一個坐標系,導致各個節(jié)點所定義的坐標系的方位與角度都并不一致。因此需要將簇內從節(jié)點的坐標軸方位調整為統(tǒng)一的Y軸正方位,并以主節(jié)點為坐標原點建立局部坐標系,從節(jié)點計算并更新自己的新坐標。

2.3.1 收發(fā)節(jié)點間方向角的計算

簇內協(xié)同需要計算節(jié)點間的方向角,每個節(jié)點通過內置的超聲波接收機或天線陣列來感知信號的到達方向并計算。圖1展示了節(jié)點A配兩個接收設備R1,R2的結構圖。R1,R2分別位于節(jié)點A的兩側等距離處,距離相隔L。節(jié)點A自身認知的坐標系統(tǒng)的Y軸即為R1,R2連線的中垂線,X軸即為R1,R2的連線。R1,R2接收到發(fā)送節(jié)點B發(fā)射過來的信號后,通過TOA技術測量出節(jié)點B分別到R1,R2的距離X1,X2,根據幾何關系,便可以計算出節(jié)點B在節(jié)點A自身認知的坐標系統(tǒng)中的方向角θ。若實際運用中有多個超聲波接收設備或天線陣列,角度計算仍按上述方法。

圖1 節(jié)點結構圖

2.3.2 簇內協(xié)同

簇內協(xié)同由主節(jié)點觸發(fā),主節(jié)點周期性地廣播消息ANGLESYNC給它的從節(jié)點。從節(jié)點根據存儲的主節(jié)點ID號接收協(xié)同信息,非主節(jié)點的協(xié)同信息將被拋棄。如圖2所示,在ANGLESYNC信息中包含角度參數,各個從節(jié)點根據該參數并發(fā)地進行角度協(xié)同。

圖2 簇內角度協(xié)同開始

圖2中,A為主節(jié)點,B,C等為從節(jié)點。利用角度測量,可得從節(jié)點B相對于主節(jié)點A的角度WAB以及主節(jié)點A相對于從節(jié)點B的角度WBA。則從節(jié)點B的調整方式按式(1)方式進行:

(1)

對于兩個協(xié)同周期內都未收到協(xié)同消息的從節(jié)點,該節(jié)點就認為其主節(jié)點處于失效狀態(tài),它將接收來自其鄰居節(jié)點的協(xié)同消息,并比較協(xié)同輪次的大小。如果鄰居節(jié)點協(xié)同信息包的協(xié)同輪次新于自己的協(xié)同輪次,它就將自己的方位同步到此鄰居節(jié)點的方位,從而達到簇內方位的協(xié)同。

2.3.3 簇內局部坐標構建

簇內各節(jié)點方位協(xié)同之后,即可構建簇內局部坐標。如圖3所示,主節(jié)點以自身為原點建立局部坐標系,于是主節(jié)點A的坐標為(0,0)。所有節(jié)點的自我認知坐標點初始化也都為(0,0)。dist(A,B)為節(jié)點A所測量到的與節(jié)點B的距離,由此可得式(2):

(2)

B′:(XB,YB)即為更新后的子節(jié)點坐標。其余從節(jié)點也依方法更新自己的局部坐標值。

圖3 簇內局部坐標系構成

2.4 全局協(xié)同

在全局坐標系構建的過程中,通過合并簇并轉換節(jié)點坐標來實現。本算法從數量少的節(jié)點簇逐步向數量多的節(jié)點簇轉換,初始時每個主節(jié)點把自己作為網絡的中心,向外廣播一條CENTER消息,在主節(jié)點間轉發(fā),從而選舉度數最大的節(jié)點作為網絡的中心。

圖4 可連通節(jié)點簇簇間方位協(xié)同前

2.4.1 兩類節(jié)點簇

在全局協(xié)同時,根據簇頭節(jié)點能否和鄰居簇中已定位的邊界節(jié)點連通將節(jié)點簇分為可連通的和不連通的兩類。兩類節(jié)點簇的簇間方位協(xié)同前的示意圖如圖4和圖5所示。其中k簇是已定位的全局簇,i簇是未定位的節(jié)點簇,需要從i簇向k簇進行轉換。在圖5中,節(jié)點m和節(jié)點j分別屬于i節(jié)點簇和主簇k并無法與其他簇主節(jié)點保持連通,但節(jié)點m和節(jié)點j之間能通信。

圖5 不可連通節(jié)點簇簇間方位協(xié)同前

圖6 節(jié)點簇的簇間協(xié)同流程

2.4.2 簇間協(xié)同

兩類節(jié)點簇的簇間協(xié)同流程如圖6所示,主要涉及兩輪協(xié)同操作。第1輪協(xié)同操作針對可連通節(jié)點簇,未同步的主節(jié)點需接收BORDER消息并計算出坐標變換所需信息(RA,ki),其中RA為方位需逆時針調整的角度,ki為主節(jié)點在全局坐標系中的坐標值(坐標均用向量表示)。之后在簇內廣播MERGE信息包,信息包中Body內包含的需逆時針調整的角度即是RA,主節(jié)點在全局坐標系中的坐標值即是ki。簇內所有節(jié)點根據此信息實現全局的方位協(xié)同,并計算出自身的全局坐標值,實現定位的節(jié)點簇加入集合S(1)。此時,如果簇內接收到MERGE信息的為邊界節(jié)點,則在計算自身的全局坐標值之后再廣播BORDER消息包,重復上述過程,直至所有符合要求的局部坐標系全部協(xié)同至全局坐標系。

若上一輪全局協(xié)同完成后,節(jié)點簇還未同步到全局節(jié)點簇,則啟動第2輪全局協(xié)同,此時操作的是不可連通的節(jié)點簇。在第1輪全局協(xié)同時,部分簇的從節(jié)點m儲存了相關信息暫時沒處理。在此輪協(xié)同階段中,圖5中的節(jié)點m計算出坐標變換所需信息(RA,km),km為節(jié)點m在全局坐標系中的坐標值。而后節(jié)點m向它的主節(jié)點i發(fā)送一個MERGE信息包,信息包中包含了(RA,km)信息。主節(jié)點i收到MERGE信息包后,將信息包中的發(fā)送節(jié)點在全局坐標系中的坐標修改成ki,然后在簇內廣播此MERGE信息包,之后的過程如同第1輪中的后續(xù)過程。同樣,實現定位的節(jié)點簇加入集合S(1)。

以上全局協(xié)同的方法完全是分布式進行的,以DISTANCE,ANGLESYNC,CENTER,BORDER,MERGE等消息驅動,各個節(jié)點根據收到的不同消息做出不同的響應動作,每個節(jié)點都有自己的周期。

2.4.3 全局坐標值的計算

①計算(RA,ki)和(RA,km)

(RA,ki)和(RA,km)的計算方法一致,此處僅說明(RA,ki)的計算。通過對BORDER信息包的Body中nodeID的查找,可發(fā)現跟自身ID一致的nodeID,對應的Angle字段即為邊界節(jié)點j監(jiān)測的主節(jié)點i的相對方向角Wji,同時主節(jié)點i可以監(jiān)測得邊界節(jié)點j的相對方向角Wij,可以得出式(3):

RA=[Wij-(Wji-π)]

(3)

式中:RA為方位需逆時針調整的角度,Wij與Wji的范圍為0～2π。

圖7 局部坐標系調整方位后邊界節(jié)點重新計算坐標

由平面坐標和極坐標之間的關系可表示為:

(4)

(5)

隨后,因為節(jié)點i和節(jié)點k的局部坐標值都為(0,0),通過如下公式可得式(6):

(6)

②簇內從節(jié)點坐標值轉換為全局坐標值

從節(jié)點根據主節(jié)點發(fā)來的MERGE信息包計算自己的全局坐標值。在主節(jié)點調整了自己的局部坐標值后,從節(jié)點的局部坐標值也需要調整,假設m是從屬于i的一個從節(jié)點,調整之前m的坐標是(x,y),調整之后m的坐標是(x′,y′)。同理,根據(x′,y′)與(x,y)之間的關系,可得調整之后m的坐標如式(7)所示:

(7)

3 仿真實驗與分析

所有的實驗環(huán)境均在二維環(huán)境下所完成,利用MATLAB中的交互式的高級編程語言—M語言完成所有的仿真實驗,為方便比較,實驗采用的參數與聚類SPA一致:地域范圍分別30 m×30 m,節(jié)點隨機分布于這個方形區(qū)域中,通信半徑為2 m。

3.1 網絡覆蓋率的比較

評價一個定位算法性能的重要方面就是看能不能實現網絡中絕大部分節(jié)點的定位,即網絡節(jié)點覆蓋率的大小。網絡覆蓋率定義為Cov=(N/M)×100%,其中M表示全網絡中傳感器節(jié)點總數,N表示定位結束后能夠獲得位置坐標的傳感器節(jié)點總數。本文所提出的CCPA算法便將網絡覆蓋率作為最主要改進的指標進行研究,無論是通過使用方位角信息,還是在全局協(xié)同階段改進兩簇合并的條件,都是為了提高網絡覆蓋率。下面對比兩種算法在低節(jié)點密度區(qū)域的性能對比,其中節(jié)點密度定義為每平方米的節(jié)點個數。

分析圖8可知,聚類SPA和本算法的網絡覆蓋率大體上都與節(jié)點密度成正比。聚類SPA算法的節(jié)點覆概率在不同節(jié)點密度下平均為35%,其中節(jié)點密度為0.28時具有最高的網絡覆蓋率為32%,而在節(jié)點密度為0.1時其覆蓋率僅為18%。而CCPA算法的平均覆蓋率為70%,其中節(jié)點密度為0.26時其覆蓋率最高約為84%,而最低的網絡覆蓋率也有39%。在相同節(jié)點密度下,相對于聚類SPA算法,CCPA算法的網絡覆蓋率提升接近一倍。聚類SPA算法在低節(jié)點密度的情形下網絡覆蓋率不高的主要原因是在建立局部坐標系階段,會出現大量節(jié)點無法找到除簇頭以外的兩個已獲取局部坐標的鄰居節(jié)點來實現定位,從而無法獲得自身局部坐標值而導致節(jié)點失效,再加上全局協(xié)同階段沒有兩個以上的邊界節(jié)點導致出現更多的失效節(jié)點,而CCPA算法采用距離加角度信息,使兩簇協(xié)同的條件放寬了很多,兩方面共同作用使得CCPA算法在低節(jié)點密度的場景下網絡覆蓋率也有一個良好的表現。

圖8 網絡覆蓋率的比較

3.2 定位誤差率的比較

接下來對算法定位誤差率進行考察,定位誤差率也是定位算法主要考慮的方面,定位誤差主要來源于距離測量誤差、角度測量誤差以及算法計算過程中的誤差累計問題。定位誤差率定義為式(8):

(8)

圖9 定位誤差率的比較

從圖9可以得出,兩個算法的定位誤差率都與節(jié)點密度成正比,兩條曲線都隨著節(jié)點密度的上升而上升。聚類SPA算法比CCPA算法上升速度要快,坡度更明顯。在節(jié)點密度小于一定程度的時候,聚類SPA算法的定位誤差率比CCPA算法要小。但在節(jié)點密度大于0.9以后,CCPA算法的定位誤差率變得比聚類SPA要小,其平均定位誤差率比聚類SPA算法減少了22.3%。產生這個現象的主要原因是聚類SPA在節(jié)點密度較低的時候網絡覆蓋率也比較低,能實現定位的這些為數不多的節(jié)點主要是位于全局中心簇附近的節(jié)點簇,其坐標的轉換次數少,導致誤差累積比較小;而CCPA在節(jié)點密度較低的時候網絡覆蓋率也比較高,離中心節(jié)點簇較遠的節(jié)點簇也能實現定位,但誤差累積相對來說比較大,因此總體上看來,在節(jié)點密度比較小的時候聚類SPA算法的定位誤差率比CCPA算法要小。然后,隨著節(jié)點密度的逐漸增大,聚類SPA也會受到離全局中心簇比較遠的節(jié)點的誤差累積的影響,而且影響的比重會逐漸加大。所以在節(jié)點密度較高的時候,CCPA算法的定位誤差率會變得比聚類SPA要小,并且差距會越來越明顯,本算法的優(yōu)勢會逐漸顯現。

定位誤差率會隨著節(jié)點密度的增長而變大。這是因為在全局協(xié)同階段會產生誤差疊加現象。誤差疊加現象指的是,由于距離測量誤差和角度測量誤差的存在而導致節(jié)點計算自身全局坐標值時會產生一定誤差,而其他未同步簇又會根據這已有一定誤差的坐標值計算自身的坐標,從而導致誤差疊加現象。因此可以推出,節(jié)點簇參與坐標轉換計算的次數越多,誤差累積越嚴重。在分簇階段CCPA算法比聚類SPA算法形成的簇的數量要少,另外在全局協(xié)同階段的全局協(xié)同策略的不同,兩方面的共同作用使得CCPA算法比聚類SPA算法減少了很多的坐標轉換次數,因此定位誤差率方面表現更好。但是由于CCPA算法比聚類SPA算法多了個角度測量誤差,兩者中和,因此改進不是特別明顯。

3.3 通信開銷的比較

在不同節(jié)點密度值下本算法和聚類SPA算法的通信量及其差距對比如圖10所示。從圖中可以看出,兩算法的通信量隨節(jié)點密度的上升呈線性增長。那是因為兩算法在簇形成階段與簇內同步階段都需要收集節(jié)點信息,節(jié)點數越多,所需的通信量越大。但聚類SPA增加的速度比本算法速度快。并且,在節(jié)點密度加劇的時候,這種差異更明顯。

圖10 通信開銷的比較

4 總結

本文提出了一種無錨節(jié)點的無線傳感器網絡協(xié)同定位算法:CCPA算法。在無錨節(jié)點存在的情況下,利用改進后的基于節(jié)點密度的分簇算法,即ICAND算法進行分簇,通過分布式的定位方式,把角度測量和距離測量結合起來,逐步對同步中的節(jié)點進行方位調整和坐標調整,從而計算出所有節(jié)點在區(qū)域坐標系統(tǒng)當中的坐標。仿真實驗數據表明,在節(jié)點隨機分布的情況下,CCPA算法在網絡覆蓋率、定位誤差率和通信開銷方面都有良好的表現,比起業(yè)界公認的聚類SPA算法,網絡覆蓋率提高了接近一倍;另外,在節(jié)點密度大于0.9時,其定位誤差率平均減少了22.3%。

[1] Byrne J A. 21 Ideas for the 21st Century[J]. Business Week,1999,8(11):78-167.

[2]Borko H,Bernier C. Emerging Technologies that Will Change the World[J]. Technology Review,2003,106(1):2249.

[3]AI-Karaki J N,Kamal A E. Routing Techniques in Wireless Sensor Networks:A Survey[J]. Wireless Communications,IEEE,Dee 2004,11(6):6-28.

[4]Motomura S,Isokawa T,Kawa H,et al. On Improvement of Anchor-Free Localization in ZigBee Sensor Network[C]//Proceedings of the 2012 Third International Conference on Networking and Computing. IEEE Computer Society,2012:362-366.

[5]Chen Yuanfang,Li Mingchun,Sun Weifeng,et al. GPS-Free and Anchor-Free Indoor Localization for Wireless Sensor Networks[J]. International Journal of Advancements in Computing Technology,2012,4(16):64-73.

[6]傅賢鋒,黃亮,黃潔,等. 基于超聲波四元陣測距的無錨節(jié)點定位算法研究[J]. 儀器儀表學報,2013,34(12):2874-2888.

[7]Emokpae L,Younis M. Surface-Reflection-Based Communication and Localization in Underwater Sensor Networks[J]. ACM Transactions on Sensor Networks(TOSN),2014,10(3):50.

[8]Shang Yi,Ruml Wheeler,Zhang Ying. Localization from Mere Connectivity[C]//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2003:201-212.

[9]劉健苗,許新忠,黃書廣,等. 改進的分布式無線傳感器網絡多維標度定位算法[J]. 傳感技術學報,2014,27(5):692-697.

[10]Capkun S,Hamdi M,Hubaux J P,et al. 2001. GPS-Free Positioning in Mobile Ad-Hoc Networks[C]//Proceedings of Hawaii International Conference on System Sciences. Maui,HW.

[11]Iyengar R,Sikdar B. Scalable and Distributed GPS Free Positioning for Sensor Networks[C]//Proc of IEEE Int’l Conf on Communications 2003. V01.1. Anchorage:IEEE Communications Society,2003,338-342.

[12]Xiaoli Li,Hongchi Slli,Yi Shang. A Map-Growing Localization Algorithm for Ad-Hoc Wireless Sensor Networks[C]//Proceedings of the Tenth International Conference on Parallel and Distributed Systems. 2004:39.

[13]Gerla M,Tsai J T C. Multicluster,Mobile,Ultimedia Radio Network[J]. Wireless Networks,1995,1(3):255-265.

[14]李德識,鐘婧. 基于節(jié)點密度的傳感器網絡路由算法研究與設計[J]. 武漢大學學報:工學版,2005,38(4):75-78.

[15]程秀芝,朱達榮,張申,等. 基于RSSI差分校正的最小二乘-擬牛頓定位算法[J]. 傳感技術學報,2014,27(1):123-127.

[16]Neal P,Joshua A N. Locating the Nodes:Cooperative Localization in Wireless Sensor Networks[J]. IEEE Signal Processing Magazine,2005,22(4):54-69.

王 明(1968-),男,副教授,全國高校計算機教學研究會理事,浙江省計算機教學研究會常務理事,寧波大紅鷹學院物聯網研究所常務副所長。近年來,承擔或參與多項省部級、市廳級課題,主持寧波市自然科學基金項目。主要研究方向為無線傳感器網絡、信息系統(tǒng)分析與設計,發(fā)表學術論文20余篇,其中11篇論文由SCI/EI/ISTP收錄,mr-wm@163.com;

陳慶章(1955-),男,教授,博士生導師,浙江工業(yè)大學計算機學院黨委書記,主要研究方向是無線傳感器網絡、分布式處理與協(xié)同工作等。主持有國家自然科學基金、浙江省重大科技攻關課題和浙江省自然科學基金等多個項目,發(fā)表學術論文50余篇,其中37篇論文由SCI/EI/ISTP收錄。

A Cooperative Node Localization Algorithm in Wireless Sensor Networks*

WangMing1,MengYun1,LiJing2,YingKeZhen3,4,ChenQingzhang3*

(1.Ningbo Dahongying University,Ningbo Zhejiang 315175,China;2.H3C Technologies Co.,Limited,Hangzhou 310053,China;3.Zhejiang University of Technology,Hangzhou 310023,China;4.Dongfang College,Zhejiang University of Finance and Economics,Haining Zhejiang 314408,China)

An anchor-free localization algorithm in wireless sensor networks is presented. Using nodes clustering and direction cooperation,the algorithm adjusts nodes’directions and coordinates with angle and range measurement to compute all nodes’ relative coordinates. Simulation results show that the network coverage,localization error rate and communication expense of the algorithm are better than clustering-based self-positioning algorithm.

wireless sensor networks;cooperative localization algorithm;anchor-free localization;nodes clustering

項目來源:寧波市自然科學基金項目(2013A610125);國家自然科學基金項目(61379023)

2014-11-25 修改日期:2015-02-05

C:6150P

10.3969/j.issn.1004-1699.2015.05.017

TP393

A

1004-1699(2015)05-0709-08