無線傳感器網絡拓撲邊界辨識算法*

顧 德，王繼帥

(1.江南大學 自動化研究所，輕工過程先進控制教育部重點實驗室，江蘇 無錫214122;2.中國科學院 蘇州生物醫學工程技術研究所，江蘇 蘇州215163)

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)由大量低值節點以自組織的方式組成網絡，十分適合應用于無人值守的情景。一些早期的研究成果常常假設WSNs 部署區域是一個凸區域，但實際應用中，如果部署區域內含有障礙物，不滿足上述假設，則會使這些算法的表現達不到預期。因此，了解部署區域幾何形狀有利于優化WSNs 工作表現，將處在WSNs 邊界的節點識別出來則是描述部署區域幾何形狀的最直觀的方法。此外，拓撲邊界是在復雜形狀的WSNs 中判斷網絡拓撲瓶頸的必備條件［1］，也是進行近凸分塊的必備條件［2，3］。

文獻中有以下幾類WSNs 邊界辨識方法:

1)基于統計的方法:Fekete S 認為如果某個節點的鄰節點數量顯著少于其他節點，那么該節點就在邊界位置［4］。但是此方法要求部署的密度達100 左右時，才能有合理的結果［5］。

2)基于拓撲的方法:Funke S 提出了一種在WSNs 中構造等距離線并通過判斷等距離線的中斷點來判斷WSNs 邊界的方法［6］。Wang Y［5］提出的方法在含有孔洞的WSNs內尋找到一部分邊界后，將邊界上的節點連接起來，以降低漏認率。Simek M［7］提出的方法也屬此類，并且漏認率較低。但是以上方法都存在較高的誤認率。

3)基于空間位置的方法:Fang Q 提出一種在WSNs 中沿某個確定的方向發送數據包，通過觀察數據包最終停留的節點來判斷邊界［8，9］。但此方法要求節點具有位置感知能力。

本文認為，在辨識WSNs 邊界時，應當優先抑制誤認率，少數誤認的邊界就將影響對WSNs 的整體判斷，而漏認少數邊界節點并不影響大局，剩余的邊界節點足以勾勒出WSNs 的分布范圍。本文將在以下假設和限制下討論完成WSNs 邊界辨識的方法:1)本算法不依賴WSNs 節點位置感知能力;2)WSNs 節點均勻隨機部署;3)短時間內，網絡節點是靜態的。

1 算法思想

在連續的標量場中，等值線的斷開處必然在物體的邊界上。例如:可以觀察到在任何一個時刻，某國氣象信息中的任意一條等溫線，要么是閉合的曲線，要么是一條連接其國界線上兩點的曲線段。所以，如果能在一個平面區域中構造一個連續的標量場，那么，尋找一個平面區域的邊界的問題就可以轉化為尋找曲線段的端點的問題。

1.1 構造連續標量場

在平面區域中構造連續標量場并不困難。例如:加熱一個固體薄片的某幾個點一段時間，這個固體中就會出現一個溫度場。此后觀察等溫線，將等溫線的端點標記出來，就可以獲得該固體薄片的邊界。

根據傅里葉定律，可以推導出該固體中任何一點的溫度變化情況

其中，?T/?t 為該點溫度隨時間的變化率，λ，c，ρ 分別為熱傳導系數、熱容、密度，Q 為單位時間內該點從系統外獲得的熱量。當該點為被加熱點時，Q 為正值常數;否則，Q=0。

根據上述公式，可以用數學的方式推演熱傳導的過程，構造連續的標量場。

1.2 辨識等值線的端點

曲線的端點具有明顯的特征，可根據以下條件判斷:以曲線上一點為圓心，r 為半徑作圓，當r→0 時，若圓與曲線只有一個交點，則圓心為曲線的端點。

這樣，在構造連續標量場并判斷出等值線的端點后，平面區域的邊界就辨識出來了。

受到這種算法思想的啟發，開發了一種新的辨識WSNs 邊界的方法。

2 WSNs 邊界辨識算法

2.1 熱傳導規律的離散化

將均勻隨機部署的WSNs 節點視為構成固體的子塊。如圖1，若節點i 與n 個其他節點相鄰，則視固體中的子塊gi與n 個其他子塊相鄰。

將公式(1)從空間上離散化，可得

其中，ΔTij為gi與gj的溫差。繼續將公式(2)在時間上離散化，可得

圖1 gi 與n 個其他子塊相鄰Fig 1 gi surrounded by n other blocks

2.2 在WSNs 中構建虛擬溫度場

在WSNs 中，隨機地挑選若干個節點作為熱源，賦予其一個正值的qi，然后按照式(4)描述的規律，在WSNs 中模擬熱傳導現象，反復進行一段時間之后，WSNs 中就構建起了虛擬的溫度場。

2.3 建立虛擬等溫線

在模擬熱傳導現象結束后，每個節點與其相鄰節點交換虛擬溫度值，選擇虛擬溫度值與其本身最為接近的若干節點作為自身的候選近似等溫點，如果雙方互相將對方選擇為候選近似等溫點，則確認該兩個節點近似等溫。在本文中選擇候選節點的數量為其鄰節點數量的30%。

在WSNs 整個網絡的各個節點之間完成近似等溫點的確認之后，網絡中就建立了虛擬等溫線，如圖2 所示。圖中，五角星表示被選為熱源的節點，連線表示確認的近似等溫線，線條表示了不同的溫度值。

圖2 虛擬等溫線Fig 2 Virtual isotherm

2.4 確定等溫線的端點

經過上一節的步驟，平面邊界的辨識問題轉換成了折線端點辨識問題。此時節點i 可以數出其等溫鄰節點數Ni，然后通過一次鄰域內的廣播，節點i 可以了解到處在同一條等溫線上的相鄰的其他節點的等溫鄰節點數，取其最小值，記為min Nneighbor。如果Ni?min Nneighbor(在下文的仿真中，判斷標準是Ni＜0.5min Nneighbor)，那么認為節點i 為等溫線的端點，亦即WSNs 的邊界節點，如圖3 所示。從辨識結果看，等溫線的端點基本上能夠勾勒出整個區域的輪廓，并且很少有遠離邊界的誤認點。

圖3 等溫線端點Fig 3 Endpoints of isotherm

3 仿真算例

圖4 是幾組仿真算例，將一些網絡圖案經二值化，以白色區域作為WSNs 的部署區域，邊界形式包括圓弧、直線段、不規則曲線。有的算例是單連通的，有些算例是含有內部空洞。仿真結果表明:本算法能夠適應各種不同的形狀。

圖4 仿真算例Fig 4 Simulated example

在以上算例中節點平均密度(平均每個節點擁有的鄰節點數量)均在12 ～14 之間，在仿真測試中發現，降低節點密度會對本文提出的算法構成一定挑戰，圖5、圖6 分別表現了當平均節點密度下降為10.9，8.9 時的辨識效果。

以上結果表明:本算法能適應的最低密度約為11 左右。

圖5 平均密度為10.9Fig 5 Average density at 10.9

圖6 平均密度為8.9Fig 6 Average density is 8.9

4 結 論

本文提出的算法是一種不依賴地理位置信息的分布式算法，具有較為廣泛的應用價值。其方法上借鑒了自然現象中的規律，對于解決同類問題具有一定的參考價值。

本文所提出的方法也有一定的不足:從原理上來講，加熱一個固體，有可能出現等溫線與物體的邊界恰好完全重合，這種可能性是無法排除的。當出現某種特殊的情形時，可能會出現全局失效。因此，的確也存在虛擬等溫線恰好與WSNs 邊界完全重合的可能。目前尚無法排除這一可能，只能說，出現這種特殊情形出現的概率極低。

［1］ Gu D，Song C，Song Z.Bottleneck recognition by virtual temperature field in wireless sensor networks［J］.Ad－Hoc and Networks Wireless Sensor，2012，15(2－4):127－150.

［2］ Zhu X J，Sarkar R，Gao J.Segmenting a sensor field:Algorithms and applications in network design［J］.ACM Transactions on Sensor Networks(TOSN)，2009，5(2):1－32.

［3］ Gu D，Song Z.Segment and organize irregular shaped sensor networks by importing a virtual scalar field［C］∥IET International Conference on Wireless Sensor Networks，2010 IET－WSNs，2010:227－232.

［4］ Fekete S，Kr?ller A，Pfisterer D，et al.Algorithmic aspects of wireless sensor networks［M］.Berlin/Heidelberg:Springer，2004:123－136.

［5］ Wang Y，Gao J，Mitchell J S B.Boundary recognition in sensor networks by topological methods［C］∥Proceedings of the 12th Annual International Conference on Mobile Computing and Networking，2006:122－133.

［6］ Funke S.Topological hole detection in wireless sensor networks and its applications［C］∥Proceedings of the 2005 Joint Workshop on foundations of Mobile Computing(DIALM－POMC)，2005:44－53.

［7］ Simek M，Bocek J，Moravek P.Optimization of boundary recognition algorithms for wireless sensor networks applications［C］∥34th International Conference on Telecommunications and Signal Processing(TSP)，2011:189－194.

［8］ Fang Q，Gao J，Guibas L J.Locating and bypassing routing holes in sensor networks［C］∥23rd Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM)，2004:2458－2468.

［9］ Fang Q，Gao J，Guibas L.Locating and bypassing holes in sensor networks［J］.Mobile Networks and Applications，2006，11(2):187－200.