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

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

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

?

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

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

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

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

無線傳感器網絡;協同定位算法;無錨節點定位;節點分簇

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

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

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

1 相關研究

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

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

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

2 無錨節點的協同式定位算法設計

2.1 算法思想

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

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

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

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

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

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

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

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

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

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

2.2 簇形成

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

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

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

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

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

2.3 簇內協同

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

2.3.1 收發節點間方向角的計算

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

圖1 節點結構圖

2.3.2 簇內協同

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

圖2 簇內角度協同開始

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

(1)

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

2.3.3 簇內局部坐標構建

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

(2)

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

圖3 簇內局部坐標系構成

2.4 全局協同

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

圖4 可連通節點簇簇間方位協同前

2.4.1 兩類節點簇

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

圖5 不可連通節點簇簇間方位協同前

圖6 節點簇的簇間協同流程

2.4.2 簇間協同

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

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

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

2.4.3 全局坐標值的計算

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

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

RA=[Wij-(Wji-π)]

(3)

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

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

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

(4)

(5)

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

(6)

②簇內從節點坐標值轉換為全局坐標值

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

(7)

3 仿真實驗與分析

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

3.1 網絡覆蓋率的比較

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

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

圖8 網絡覆蓋率的比較

3.2 定位誤差率的比較

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

(8)

圖9 定位誤差率的比較

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

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

3.3 通信開銷的比較

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

圖10 通信開銷的比較

4 總結

本文提出了一種無錨節點的無線傳感器網絡協同定位算法:CCPA算法。在無錨節點存在的情況下,利用改進后的基于節點密度的分簇算法,即ICAND算法進行分簇,通過分布式的定位方式,把角度測量和距離測量結合起來,逐步對同步中的節點進行方位調整和坐標調整,從而計算出所有節點在區域坐標系統當中的坐標。仿真實驗數據表明,在節點隨機分布的情況下,CCPA算法在網絡覆蓋率、定位誤差率和通信開銷方面都有良好的表現,比起業界公認的聚類SPA算法,網絡覆蓋率提高了接近一倍;另外,在節點密度大于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]傅賢鋒,黃亮,黃潔,等. 基于超聲波四元陣測距的無錨節點定位算法研究[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]李德識,鐘婧. 基于節點密度的傳感器網絡路由算法研究與設計[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-),男,副教授,全國高校計算機教學研究會理事,浙江省計算機教學研究會常務理事,寧波大紅鷹學院物聯網研究所常務副所長。近年來,承擔或參與多項省部級、市廳級課題,主持寧波市自然科學基金項目。主要研究方向為無線傳感器網絡、信息系統分析與設計,發表學術論文20余篇,其中11篇論文由SCI/EI/ISTP收錄,mr-wm@163.com;

陳慶章(1955-),男,教授,博士生導師,浙江工業大學計算機學院黨委書記,主要研究方向是無線傳感器網絡、分布式處理與協同工作等。主持有國家自然科學基金、浙江省重大科技攻關課題和浙江省自然科學基金等多個項目,發表學術論文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