葛玉君

（江南大學(xué)，江蘇 無錫 214122）

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）[1-2]在生活中應(yīng)用廣泛。邊界檢測(cè)主要基于位置[3]、基于統(tǒng)計(jì)[4]、基于連接[5]?；谖恢门c統(tǒng)計(jì)的方法，要么需要傳感器精確的坐標(biāo)信息，代價(jià)昂貴；要么要求高節(jié)點(diǎn)密度，精度與網(wǎng)絡(luò)普適性差?；谶B接性的方法，實(shí)現(xiàn)成本低于位置方法，精度優(yōu)于統(tǒng)計(jì)方法，適用性強(qiáng)。本文提出的算法基于兩跳鄰居節(jié)點(diǎn)的連接信息。引入的中心性方法，常用來判斷節(jié)點(diǎn)的重要性，識(shí)別WSN邊界是其副產(chǎn)品[6]。通過計(jì)算中介中心性，量化節(jié)點(diǎn)重要程度。仿真表明，在邊界識(shí)別問題上有良好的適用性。

1 中介中心性

1.1 概念

最著名的中間度量為Freeman[7]首次在圖論中引入的中介中心性，將中心性與信息控制相聯(lián)系，描述一個(gè)節(jié)點(diǎn)被其他節(jié)點(diǎn)的需要程度[8]。

其中，σst為節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑數(shù)量，σst(v)為從節(jié)點(diǎn)s到t的所有最短路徑中經(jīng)過節(jié)點(diǎn)v的最短路徑的數(shù)目。由定義求解中心性過于復(fù)雜，故通過引入節(jié)點(diǎn)對(duì)依賴值對(duì)定義實(shí)現(xiàn)簡(jiǎn)化[9]。據(jù)此Brands提出目前已知的最快的算法。

1.2 中心性與邊界的關(guān)系

由定義知，節(jié)點(diǎn)的中介中心性越大，越可能靠近網(wǎng)絡(luò)中心[10]，反之，中心性值越小，成為邊界節(jié)點(diǎn)的概率就越大。WSN中，高中心性節(jié)點(diǎn)（圖1中節(jié)點(diǎn)1）可促進(jìn)節(jié)點(diǎn)間直接或間接通信，對(duì)從任何節(jié)點(diǎn)開始的信息流都至關(guān)重要?；谶@一發(fā)現(xiàn)，可以通過計(jì)算節(jié)點(diǎn)的中心性值從而確定邊界節(jié)點(diǎn)。

圖1 簡(jiǎn)單網(wǎng)絡(luò)

2 算法介紹

2.1 模型假設(shè)

WSN由G(V,E)表示，其中V為節(jié)點(diǎn)集，E是連接節(jié)點(diǎn)邊的集合。節(jié)點(diǎn)i的k跳領(lǐng)域圖，使用Gi(Vi,Ei)表示。節(jié)點(diǎn)均具各向同性且ID信息唯一?？紤]實(shí)際應(yīng)用中環(huán)境的友好程度，傳感器均勻分布在感知區(qū)域，可具任意形狀的通信范圍。

2.2 算法實(shí)現(xiàn)

精確計(jì)算大型網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性，其網(wǎng)絡(luò)和計(jì)算成本及其昂貴。在實(shí)際WSN中算法復(fù)雜度隨節(jié)點(diǎn)數(shù)增加而增加，如鄰接矩陣的規(guī)模即達(dá)到O(N2)。因此將全局問題轉(zhuǎn)化為局部求解。如表1所示，k從2開始取。算法主要思想是，基于邊界節(jié)點(diǎn)的中心性值較低。對(duì)節(jié)點(diǎn)對(duì)之間的路徑計(jì)算，主要通過最短路徑算法（不考慮多次經(jīng)過同一個(gè)節(jié)點(diǎn)的情況）。故對(duì)邊界識(shí)別問題，采用近似化算法，進(jìn)行分布式檢測(cè)。先為每個(gè)傳感器構(gòu)建其k跳鄰域圖，根據(jù)鄰域圖計(jì)算節(jié)點(diǎn)的中介中心性。再比較中心性的值選擇值較低的節(jié)點(diǎn)為邊界節(jié)點(diǎn)。

表1 不同k值的節(jié)點(diǎn)中心性

3 仿真與分析

為便于仿真，假設(shè)節(jié)點(diǎn)的通信區(qū)域?yàn)橐怨?jié)點(diǎn)為中心的圓，通信半徑rc，在圖上僅標(biāo)注通過算法識(shí)別的邊界節(jié)點(diǎn)。

3.1 不同k值

圖2為k取不同值時(shí)所得結(jié)果，WSN總節(jié)點(diǎn)數(shù)為3 236，平均節(jié)點(diǎn)密度為12。實(shí)驗(yàn)表明僅使用原始計(jì)算的小部分，結(jié)果就具很高的有效性。另一方面，由于算法的復(fù)雜度主要在于k跳領(lǐng)域圖內(nèi)的節(jié)點(diǎn)數(shù)，故當(dāng)k取值越小，其算法復(fù)雜度也越小。表2為k取不同值時(shí)的誤認(rèn)率情況。在節(jié)點(diǎn)密度恒定的網(wǎng)絡(luò)中，通過算法運(yùn)行時(shí)間和邊界誤認(rèn)率的綜合比較，證明2-中介中心性測(cè)度是較好的中心性近似選擇，且對(duì)于邊界識(shí)別算法具有較好的使用性。

圖2 不同k值結(jié)果

表2 不同k值誤認(rèn)率

故對(duì)于每個(gè)節(jié)點(diǎn)，只使用k個(gè)步驟來計(jì)算最短路徑，通過BFS算法遍歷每個(gè)節(jié)點(diǎn)的k跳鄰居節(jié)點(diǎn)，節(jié)省大量計(jì)算時(shí)間，且對(duì)結(jié)果度量的影響最小。

3.2 不同形狀的邊界

WSN平均節(jié)點(diǎn)密度為10，k取2，在不同形狀邊界的網(wǎng)絡(luò)中，結(jié)果如圖3所示。左圖為網(wǎng)絡(luò)部署，右圖為檢測(cè)出的邊界。結(jié)果表明，本算法適用性較強(qiáng)，對(duì)不同形狀的邊界均適用良好。

圖3 不同邊界形狀的WSN

4 結(jié)語

本文提出一種邊界識(shí)別算法，通過引入中心性概念識(shí)別出邊界點(diǎn)。綜合考慮算法的復(fù)雜度與結(jié)果的誤認(rèn)率，選擇通過節(jié)點(diǎn)的2-中介中心性，從而找到WSN邊界節(jié)點(diǎn)。