顧 德，王繼帥

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

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)常用于收集某一特定區(qū)域內(nèi)的信息，將信息匯總到數(shù)據(jù)融合中心之后與互聯(lián)網(wǎng)相連。因此，數(shù)據(jù)融合中心是WSNs 的核心［1，2］，在一個(gè)特定的應(yīng)用中數(shù)據(jù)融合中心的數(shù)量和位置對(duì)整個(gè)網(wǎng)絡(luò)能否達(dá)到預(yù)期的性能表現(xiàn)有著極為重要的影響。

WSNs 部署區(qū)域的幾何形狀對(duì)網(wǎng)絡(luò)自組織、路由、信息處理等過(guò)程有著深刻影響，瓶頸將導(dǎo)致工作負(fù)荷不均衡部分節(jié)點(diǎn)能耗過(guò)高和信道擁塞延遲加劇等問(wèn)題［3，4］。如果能將WSNs 部署區(qū)域分割成若干凸的子區(qū)域，在每個(gè)子區(qū)域的中心放置一個(gè)數(shù)據(jù)融合中心，就能廻避由幾何形狀帶來(lái)的問(wèn)題。

如果能獲取整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的位置信息對(duì)完成上述任務(wù)極為有利。然而，WSNs 本身的特點(diǎn)決定了很難創(chuàng)造出這樣的有利條件。首先，索求全局信息能量和時(shí)間代價(jià)很高;其次，絕對(duì)定位系統(tǒng)(如GPS)會(huì)增加WSNs 節(jié)點(diǎn)的成本和能耗，而相對(duì)定位目前也仍然是WSNs 的研究話題。

本文的研究就是在每個(gè)WSNs 節(jié)點(diǎn)都只擁有本身和相鄰節(jié)點(diǎn)的局部信息并且不需要位置信息的限制下，試圖將一個(gè)復(fù)雜形狀的WSNs 部署區(qū)域進(jìn)行近凸分割，并尋找到分割后的每個(gè)子區(qū)域的中心位置放置數(shù)據(jù)融合中心。

Zhu X J 等人［5］在相似的假設(shè)和限制下提出了一種分割算法，但此算法需要完美的邊界識(shí)別結(jié)果為前提，并且在某些情況下，完全相同的節(jié)點(diǎn)部署，只交換節(jié)點(diǎn)ID 排序，就導(dǎo)致分割結(jié)果完全不同。盡管存在以上不足，該論文對(duì)本文算法思想的形成起到了啟發(fā)作用。

1 算法思想的來(lái)源

本文所提出的算法受到一次對(duì)熱傳導(dǎo)現(xiàn)象觀察的啟發(fā):一個(gè)不規(guī)則外形的各向同性的均勻高溫(TH)固體被放入大量充分?jǐn)嚢璧睦渌?假設(shè)冷水的溫度始終保持不變)。最初，固體表面迅速降溫到冷水的溫度(TL)，內(nèi)部仍然保持高溫;由于熱傳導(dǎo)作用，固體內(nèi)部逐漸降溫;最終，整個(gè)固體降溫到冷水溫度。

在溫度逐漸變化的過(guò)程，記點(diǎn)P(x，y，z)在時(shí)間t 的溫度是T(x，y，z，t)。給定時(shí)間t，則溫度場(chǎng)的梯度為

溫度梯度與等溫面垂直并指向高溫處。傅立葉定律指出

其中，q 為熱通量，λ 為導(dǎo)熱系數(shù)。記固體的密度為ρ，比熱容為c，導(dǎo)熱系數(shù)為λ，根據(jù)式(1)和式(2)，可求點(diǎn)P(x，y，z)隨時(shí)間t 變化的規(guī)律

熱固體降溫過(guò)程中，以下性質(zhì)值得注意:

1)由于存在確定的初始條件(固體內(nèi)部溫度均為TH)和固定邊界條件(整個(gè)過(guò)程中固表面始終保持TL)，式(3)對(duì)于任何P 和任何t 有定解，即可以獲得在任意時(shí)間的溫度分布，如圖1 所示。

圖1 某時(shí)刻溫度場(chǎng)分布(深色表示高溫)Fig 1 Distribution of temperature field at one time(darker color indicates hight temperature)

2)熱傳導(dǎo)需要媒質(zhì)，只要獲取P(x，y，z)鄰域內(nèi)點(diǎn)的溫度信息就能計(jì)算P 的溫度變化。

3)由于固體表面是最低溫TL的等溫面，溫度梯度線都指向內(nèi)部，并均將終止于極大值點(diǎn)。

4)匯聚到不同極大值點(diǎn)的溫度梯度線將整個(gè)溫度場(chǎng)分割成若干近凸分塊。

5)這些極大值點(diǎn)都接近分塊的中心位置。

以上性質(zhì)分別說(shuō)明:溫度分布的變化可以通過(guò)數(shù)學(xué)計(jì)算模擬，模擬過(guò)程中只需要獲得鄰域內(nèi)的溫度分布;溫度梯度線可以幫助完成區(qū)域分割;分塊中心可由極大值點(diǎn)找到。

2 網(wǎng)絡(luò)融合中心選址方法

2.1 確定WSNs 邊界

首先，應(yīng)當(dāng)選擇Wang Y［6］，Saukh O［7］或顧德［8］在其論文中提出的算法確定WSNs 的邊界。處在邊界上的點(diǎn)的虛擬溫度始終固定在TL，其他點(diǎn)的虛擬溫度賦予初值TH，其中TH＞TL。

2.2 模擬熱傳導(dǎo)過(guò)程

將傳感器節(jié)點(diǎn)視為固體塊中的一個(gè)微小子塊，用節(jié)點(diǎn)間的單跳通信關(guān)系模擬固體中微小子塊間的相鄰關(guān)系。假設(shè)某個(gè)節(jié)點(diǎn)bi與n 個(gè)其他節(jié)點(diǎn)相鄰，記節(jié)點(diǎn)bi的虛擬溫度值為Ti，其相鄰節(jié)點(diǎn)b1，b2，…，bn的虛擬溫度值分別為T1，T2，…，Tn。將式(3)在空間上離散化可得

進(jìn)一步在時(shí)間上離散化可得

完成若干次迭代之后，在整個(gè)WSNs 中就建立了虛擬溫度場(chǎng)。

2.3 虛擬梯度線和極大值

在上文中建立的虛擬離散溫度場(chǎng)中，設(shè)Tj=max(T1，T2，…，Tn，Ti)，若i≠j，則bj是bi的鄰節(jié)點(diǎn)中虛擬溫度值最大的節(jié)點(diǎn)是由bi指向bj的梯度線;若i=j，則bi是虛擬溫度的局部極大值點(diǎn)。

2.4 完成WSNs 部署區(qū)域的分割和融合中心選址

如果將梯度線視為節(jié)點(diǎn)間唯一存在的拓?fù)潢P(guān)系，那么，整個(gè)網(wǎng)絡(luò)就成為若干以虛擬溫度極大值節(jié)點(diǎn)為根節(jié)點(diǎn)樹形網(wǎng)絡(luò)。這些樹形網(wǎng)絡(luò)把原有的復(fù)雜形狀的WSNs 分割成若干近凸分塊，并且樹的根節(jié)點(diǎn)接近整個(gè)分塊中心，可以選擇作為融合中心放置的位置。與K-means 算法［9］(取k=5，并擁有全局節(jié)點(diǎn)位置信息)求得的最優(yōu)解相比，5 個(gè)根節(jié)點(diǎn)距離最優(yōu)解的平均距離是單跳通信距離的0.21 倍，已接近數(shù)據(jù)融合中心的最優(yōu)選址。

圖2 演示了整個(gè)算法過(guò)程，在(a)～(g)中用Z 軸表示虛擬溫度值，折線表示溫度梯度線。(a)為最初階段;(b)～(g)非邊界節(jié)點(diǎn)根據(jù)式(6)迭代，最終獲得如(g)中所示的結(jié)果;(g)在水平面上的投影如(h)所示，整個(gè)網(wǎng)絡(luò)被分割成若干拓?fù)錁?，完成了近凸分塊，并且根節(jié)點(diǎn)均處于接近所在分塊中心的位置。(g)，(h)圖中，兩個(gè)不同拓?fù)錁涞慕唤缥恢糜脠A點(diǎn)標(biāo)出。

2.5 算法復(fù)雜度分析

以下分析從確定WSNs 邊界開(kāi)始，直至算法完成的復(fù)雜度。

圖2 算法運(yùn)行過(guò)程示意，圖中的線段表示虛擬溫度梯度線Fig 2 Operation process of algorithm，lines in this demo represent gradients of virtual temperature

對(duì)于一個(gè)特定的節(jié)點(diǎn)，用式(6)模擬熱傳導(dǎo)的過(guò)程中，每個(gè)節(jié)點(diǎn)需要的完成O(n)次通信，耗時(shí)為O(1)，其中，n為平均節(jié)點(diǎn)密度(即平均每個(gè)節(jié)點(diǎn)擁有的鄰節(jié)點(diǎn)數(shù)量)。根據(jù)虛擬溫度梯度尋找拓?fù)錁涞母腹?jié)點(diǎn)的過(guò)程，每個(gè)節(jié)點(diǎn)需要的完成O(n)次通信，耗時(shí)為O(1)。拓?fù)錁涞母?jié)點(diǎn)將其身份信息傳遞到屬于該樹的所有節(jié)點(diǎn)的過(guò)程，每個(gè)節(jié)點(diǎn)需要完成至多O(n)次通信，耗時(shí)為O(1)。

以上所有過(guò)程中，節(jié)點(diǎn)需要獲取和存儲(chǔ)的信息僅限于鄰節(jié)點(diǎn)的ID 和當(dāng)前的虛擬溫度值，所以，需要的存儲(chǔ)空間為O(n)。

綜上，為了本文所提出的算法，每個(gè)節(jié)點(diǎn)總共需要耗費(fèi)的通信次數(shù)為O(n)，耗時(shí)為O(1)，需占用的存儲(chǔ)空間為O(n)。由于遍歷鄰節(jié)點(diǎn)不可避免，所以，在復(fù)雜度的數(shù)量級(jí)上已沒(méi)有繼續(xù)優(yōu)化的可能。

3 仿真與分析

3.1 邊界識(shí)別部分缺失的影響

圖2(h)是在邊界完整的條件下獲得的結(jié)果，但是邊界識(shí)別問(wèn)題目前還無(wú)法滿足這一要求。

圖3 所示的算例中，節(jié)點(diǎn)分布情況與圖2(h)完全相同，但隨機(jī)地將邊界節(jié)點(diǎn)中的一部分設(shè)定為非邊界節(jié)點(diǎn)。圖3(a)是邊界漏認(rèn)60%時(shí)的結(jié)果，與圖2(h)相差不大;圖3(b)，(c)，分別是邊界漏認(rèn)65%和70%時(shí)的結(jié)果，分塊數(shù)量增多，樹的根節(jié)點(diǎn)位置明顯偏離分塊中心。對(duì)不同比例的邊界漏認(rèn)分別做20 次實(shí)驗(yàn)，把出現(xiàn)形如圖3(b)，(c)的分塊錯(cuò)誤的次數(shù)記錄下來(lái)，得到圖4。

圖3 不完整邊界的影響Fig 3 Impact of imperfect boundary

圖4 分塊錯(cuò)誤與邊界漏認(rèn)的關(guān)系Fig 4 Relationship between block error and boundary missing

分析以上仿真結(jié)果，當(dāng)漏認(rèn)率較低時(shí)，被漏認(rèn)的邊界節(jié)點(diǎn)零散地出現(xiàn);漏認(rèn)逐漸增多，邊界節(jié)點(diǎn)連續(xù)漏認(rèn)的概率緩慢增高，當(dāng)超過(guò)某個(gè)臨界值時(shí)，漏認(rèn)節(jié)點(diǎn)形成連續(xù)的漏認(rèn)鏈條的概率急劇增加，在漏認(rèn)鏈條的中點(diǎn)附近就會(huì)出現(xiàn)一個(gè)局部極大值點(diǎn)，導(dǎo)致分塊錯(cuò)誤。由于臨界值高達(dá)60%左右，可認(rèn)為本算法對(duì)于邊界漏認(rèn)有足夠容忍度，能夠應(yīng)對(duì)邊界識(shí)別不完整。

3.2 節(jié)點(diǎn)部署密度的影響

在第2 節(jié)有“均勻”和“各向同性”的假設(shè)。當(dāng)節(jié)點(diǎn)部署很密集時(shí)，這兩個(gè)假設(shè)基本成立;如果密度下降，則將背離這兩個(gè)假設(shè)，后面的分析和設(shè)計(jì)就有可能不正確。

圖2(h)的平均節(jié)點(diǎn)密度是10.2，逐漸降低部署的節(jié)點(diǎn)數(shù)量。圖5(a)所示的算例平均密度為8.1;(b)所示的算例平均密度為6.4，該密度下部分算例出現(xiàn)多余分塊，拓?fù)錁涞母?jié)點(diǎn)也明顯偏離分塊的中心;(c)所示的算例平均密度為4.4，幾乎所有算例都出現(xiàn)分塊錯(cuò)誤，拓?fù)錁涓?jié)點(diǎn)也經(jīng)常不在節(jié)點(diǎn)中心。

圖5 部署密度的影響Fig 5 Impact of deployment density

設(shè)大量算例中5%的算例出現(xiàn)錯(cuò)誤的平均密度為密度臨界值，那么仿真實(shí)驗(yàn)表明:密度臨界值在7.1～8.0 之間。

3.3 各種不同的形狀

將本文提出的算法應(yīng)用到各種不同形狀的WSNs 中，則獲得了如圖6 結(jié)果，平均節(jié)點(diǎn)密度均在10 左右，融合中心選址與利用全局信息求得的最優(yōu)選址的距離如表1 所示。

從表1 中可以發(fā)現(xiàn)，各算例中的根節(jié)點(diǎn)與最優(yōu)選址之間的平均距離都不到單跳通信距離。這說(shuō)明本算法中各個(gè)根節(jié)點(diǎn)可作為網(wǎng)絡(luò)融合中心的選址。

圖6 各種不同形狀WSNs 融合中心的選址結(jié)果Fig 6 Fusion center positioning result of different shapes WSNs

表1 各算例根節(jié)點(diǎn)距離最優(yōu)選址的平均距離(以單跳通信距離的倍數(shù)計(jì))Tab 1 Average distance of the optimal positions of each example rootnodes(counts by multiple of communication distance of single hop)

4 結(jié) 論

本文受熱傳導(dǎo)現(xiàn)象的啟發(fā)，在WSNs 中模擬熱傳導(dǎo)的過(guò)程，通過(guò)觀察某時(shí)刻的溫度場(chǎng)合溫度梯度，對(duì)復(fù)雜形狀的WSNs 進(jìn)行近凸分割，并找到各分塊的中心。

通過(guò)仿真實(shí)驗(yàn)，考察了本算法對(duì)于不完整邊界識(shí)別、低密度網(wǎng)絡(luò)以及各種幾何形狀的容忍程度，驗(yàn)證了算法的適應(yīng)性和實(shí)用性。

［1］ Karl H，Willig A.Protocols and architectures for wireless sensor networks［M］.Hoboken:John Wiley＆Sons，2007.

［2］ Akyildiz I F，Kasimoglu I H.Wireless Sensor and actor networks:Research challenges［J］.Ad Hoc Networks，2004，2(4):351－367.

［3］ Shin K，Lee H，Cho D-H.Diba:Distributed bottleneck alleviation scheme in wireless multi-hop sensor networks［J］.IEEE Communications Letters，2014，18(3):431－434.

［4］ Gou H，Yoo Y.Distributed bottleneck node detection in wireless sensor networks［C］∥IEEE 10th International Conference on Computer and Information Technology(CIT)，2010:218－224.

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

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

［7］ Saukh O，Sauter R，Gauger M，et al.On boundary recognition without location information in wireless sensor networks［J］.ACM Transactions on Sensor Networks(TOSN)，2010，6(3):1－35.

［8］ 顧 德，王繼帥.無(wú)線傳感器網(wǎng)絡(luò)拓?fù)溥吔绫孀R(shí)算法［J］.傳感器與微系統(tǒng)，2015，34(6):123－125.

［9］ MacQueen J B.Some methods for classification and analysis of multivariate observations［C］∥Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability，1967:281－297.