無線傳感器網(wǎng)絡(luò)拓?fù)溥吔绫孀R算法*

顧 德，王繼帥

(1.江南大學(xué) 自動(dòng)化研究所，輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫214122;2.中國科學(xué)院 蘇州生物醫(yī)學(xué)工程技術(shù)研究所，江蘇 蘇州215163)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)由大量低值節(jié)點(diǎn)以自組織的方式組成網(wǎng)絡(luò)，十分適合應(yīng)用于無人值守的情景。一些早期的研究成果常常假設(shè)WSNs 部署區(qū)域是一個(gè)凸區(qū)域，但實(shí)際應(yīng)用中，如果部署區(qū)域內(nèi)含有障礙物，不滿足上述假設(shè)，則會(huì)使這些算法的表現(xiàn)達(dá)不到預(yù)期。因此，了解部署區(qū)域幾何形狀有利于優(yōu)化WSNs 工作表現(xiàn)，將處在WSNs 邊界的節(jié)點(diǎn)識別出來則是描述部署區(qū)域幾何形狀的最直觀的方法。此外，拓?fù)溥吔缡窃趶?fù)雜形狀的WSNs 中判斷網(wǎng)絡(luò)拓?fù)淦款i的必備條件［1］，也是進(jìn)行近凸分塊的必備條件［2，3］。

文獻(xiàn)中有以下幾類WSNs 邊界辨識方法:

1)基于統(tǒng)計(jì)的方法:Fekete S 認(rèn)為如果某個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)數(shù)量顯著少于其他節(jié)點(diǎn)，那么該節(jié)點(diǎn)就在邊界位置［4］。但是此方法要求部署的密度達(dá)100 左右時(shí)，才能有合理的結(jié)果［5］。

2)基于拓?fù)涞姆椒?Funke S 提出了一種在WSNs 中構(gòu)造等距離線并通過判斷等距離線的中斷點(diǎn)來判斷WSNs 邊界的方法［6］。Wang Y［5］提出的方法在含有孔洞的WSNs內(nèi)尋找到一部分邊界后，將邊界上的節(jié)點(diǎn)連接起來，以降低漏認(rèn)率。Simek M［7］提出的方法也屬此類，并且漏認(rèn)率較低。但是以上方法都存在較高的誤認(rèn)率。

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

本文認(rèn)為，在辨識WSNs 邊界時(shí)，應(yīng)當(dāng)優(yōu)先抑制誤認(rèn)率，少數(shù)誤認(rèn)的邊界就將影響對WSNs 的整體判斷，而漏認(rèn)少數(shù)邊界節(jié)點(diǎn)并不影響大局，剩余的邊界節(jié)點(diǎn)足以勾勒出WSNs 的分布范圍。本文將在以下假設(shè)和限制下討論完成WSNs 邊界辨識的方法:1)本算法不依賴WSNs 節(jié)點(diǎn)位置感知能力;2)WSNs 節(jié)點(diǎn)均勻隨機(jī)部署;3)短時(shí)間內(nèi)，網(wǎng)絡(luò)節(jié)點(diǎn)是靜態(tài)的。

1 算法思想

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

1.1 構(gòu)造連續(xù)標(biāo)量場

在平面區(qū)域中構(gòu)造連續(xù)標(biāo)量場并不困難。例如:加熱一個(gè)固體薄片的某幾個(gè)點(diǎn)一段時(shí)間，這個(gè)固體中就會(huì)出現(xiàn)一個(gè)溫度場。此后觀察等溫線，將等溫線的端點(diǎn)標(biāo)記出來，就可以獲得該固體薄片的邊界。

根據(jù)傅里葉定律，可以推導(dǎo)出該固體中任何一點(diǎn)的溫度變化情況

其中，?T/?t 為該點(diǎn)溫度隨時(shí)間的變化率，λ，c，ρ 分別為熱傳導(dǎo)系數(shù)、熱容、密度，Q 為單位時(shí)間內(nèi)該點(diǎn)從系統(tǒng)外獲得的熱量。當(dāng)該點(diǎn)為被加熱點(diǎn)時(shí)，Q 為正值常數(shù);否則，Q=0。

根據(jù)上述公式，可以用數(shù)學(xué)的方式推演熱傳導(dǎo)的過程，構(gòu)造連續(xù)的標(biāo)量場。

1.2 辨識等值線的端點(diǎn)

曲線的端點(diǎn)具有明顯的特征，可根據(jù)以下條件判斷:以曲線上一點(diǎn)為圓心，r 為半徑作圓，當(dāng)r→0 時(shí)，若圓與曲線只有一個(gè)交點(diǎn)，則圓心為曲線的端點(diǎn)。

這樣，在構(gòu)造連續(xù)標(biāo)量場并判斷出等值線的端點(diǎn)后，平面區(qū)域的邊界就辨識出來了。

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

2 WSNs 邊界辨識算法

2.1 熱傳導(dǎo)規(guī)律的離散化

將均勻隨機(jī)部署的WSNs 節(jié)點(diǎn)視為構(gòu)成固體的子塊。如圖1，若節(jié)點(diǎn)i 與n 個(gè)其他節(jié)點(diǎn)相鄰，則視固體中的子塊gi與n 個(gè)其他子塊相鄰。

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

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

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

2.2 在WSNs 中構(gòu)建虛擬溫度場

在WSNs 中，隨機(jī)地挑選若干個(gè)節(jié)點(diǎn)作為熱源，賦予其一個(gè)正值的qi，然后按照式(4)描述的規(guī)律，在WSNs 中模擬熱傳導(dǎo)現(xiàn)象，反復(fù)進(jìn)行一段時(shí)間之后，WSNs 中就構(gòu)建起了虛擬的溫度場。

2.3 建立虛擬等溫線

在模擬熱傳導(dǎo)現(xiàn)象結(jié)束后，每個(gè)節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)交換虛擬溫度值，選擇虛擬溫度值與其本身最為接近的若干節(jié)點(diǎn)作為自身的候選近似等溫點(diǎn)，如果雙方互相將對方選擇為候選近似等溫點(diǎn)，則確認(rèn)該兩個(gè)節(jié)點(diǎn)近似等溫。在本文中選擇候選節(jié)點(diǎn)的數(shù)量為其鄰節(jié)點(diǎn)數(shù)量的30%。

在WSNs 整個(gè)網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)之間完成近似等溫點(diǎn)的確認(rèn)之后，網(wǎng)絡(luò)中就建立了虛擬等溫線，如圖2 所示。圖中，五角星表示被選為熱源的節(jié)點(diǎn)，連線表示確認(rèn)的近似等溫線，線條表示了不同的溫度值。

圖2 虛擬等溫線Fig 2 Virtual isotherm

2.4 確定等溫線的端點(diǎn)

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

圖3 等溫線端點(diǎn)Fig 3 Endpoints of isotherm

3 仿真算例

圖4 是幾組仿真算例，將一些網(wǎng)絡(luò)圖案經(jīng)二值化，以白色區(qū)域作為WSNs 的部署區(qū)域，邊界形式包括圓弧、直線段、不規(guī)則曲線。有的算例是單連通的，有些算例是含有內(nèi)部空洞。仿真結(jié)果表明:本算法能夠適應(yīng)各種不同的形狀。

圖4 仿真算例Fig 4 Simulated example

在以上算例中節(jié)點(diǎn)平均密度(平均每個(gè)節(jié)點(diǎn)擁有的鄰節(jié)點(diǎn)數(shù)量)均在12 ～14 之間，在仿真測試中發(fā)現(xiàn)，降低節(jié)點(diǎn)密度會(huì)對本文提出的算法構(gòu)成一定挑戰(zhàn)，圖5、圖6 分別表現(xiàn)了當(dāng)平均節(jié)點(diǎn)密度下降為10.9，8.9 時(shí)的辨識效果。

以上結(jié)果表明:本算法能適應(yīng)的最低密度約為11 左右。

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

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

4 結(jié) 論

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

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

［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.