基于虛擬標量場的WSNs 融合中心選址方法*

顧 德，王繼帥

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

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)常用于收集某一特定區域內的信息，將信息匯總到數據融合中心之后與互聯網相連。因此，數據融合中心是WSNs 的核心［1，2］，在一個特定的應用中數據融合中心的數量和位置對整個網絡能否達到預期的性能表現有著極為重要的影響。

WSNs 部署區域的幾何形狀對網絡自組織、路由、信息處理等過程有著深刻影響，瓶頸將導致工作負荷不均衡部分節點能耗過高和信道擁塞延遲加劇等問題［3，4］。如果能將WSNs 部署區域分割成若干凸的子區域，在每個子區域的中心放置一個數據融合中心，就能廻避由幾何形狀帶來的問題。

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

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

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

1 算法思想的來源

本文所提出的算法受到一次對熱傳導現象觀察的啟發:一個不規則外形的各向同性的均勻高溫(TH)固體被放入大量充分攪拌的冷水中(假設冷水的溫度始終保持不變)。最初，固體表面迅速降溫到冷水的溫度(TL)，內部仍然保持高溫;由于熱傳導作用，固體內部逐漸降溫;最終，整個固體降溫到冷水溫度。

在溫度逐漸變化的過程，記點P(x，y，z)在時間t 的溫度是T(x，y，z，t)。給定時間t，則溫度場的梯度為

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

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

熱固體降溫過程中，以下性質值得注意:

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

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

2)熱傳導需要媒質，只要獲取P(x，y，z)鄰域內點的溫度信息就能計算P 的溫度變化。

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

4)匯聚到不同極大值點的溫度梯度線將整個溫度場分割成若干近凸分塊。

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

以上性質分別說明:溫度分布的變化可以通過數學計算模擬，模擬過程中只需要獲得鄰域內的溫度分布;溫度梯度線可以幫助完成區域分割;分塊中心可由極大值點找到。

2 網絡融合中心選址方法

2.1 確定WSNs 邊界

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

2.2 模擬熱傳導過程

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

進一步在時間上離散化可得

完成若干次迭代之后，在整個WSNs 中就建立了虛擬溫度場。

2.3 虛擬梯度線和極大值

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

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

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

圖2 演示了整個算法過程，在(a)～(g)中用Z 軸表示虛擬溫度值，折線表示溫度梯度線。(a)為最初階段;(b)～(g)非邊界節點根據式(6)迭代，最終獲得如(g)中所示的結果;(g)在水平面上的投影如(h)所示，整個網絡被分割成若干拓撲樹，完成了近凸分塊，并且根節點均處于接近所在分塊中心的位置。(g)，(h)圖中，兩個不同拓撲樹的交界位置用圓點標出。

2.5 算法復雜度分析

以下分析從確定WSNs 邊界開始，直至算法完成的復雜度。

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

對于一個特定的節點，用式(6)模擬熱傳導的過程中，每個節點需要的完成O(n)次通信，耗時為O(1)，其中，n為平均節點密度(即平均每個節點擁有的鄰節點數量)。根據虛擬溫度梯度尋找拓撲樹的父節點的過程，每個節點需要的完成O(n)次通信，耗時為O(1)。拓撲樹的根節點將其身份信息傳遞到屬于該樹的所有節點的過程，每個節點需要完成至多O(n)次通信，耗時為O(1)。

以上所有過程中，節點需要獲取和存儲的信息僅限于鄰節點的ID 和當前的虛擬溫度值，所以，需要的存儲空間為O(n)。

綜上，為了本文所提出的算法，每個節點總共需要耗費的通信次數為O(n)，耗時為O(1)，需占用的存儲空間為O(n)。由于遍歷鄰節點不可避免，所以，在復雜度的數量級上已沒有繼續優化的可能。

3 仿真與分析

3.1 邊界識別部分缺失的影響

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

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

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

圖4 分塊錯誤與邊界漏認的關系Fig 4 Relationship between block error and boundary missing

分析以上仿真結果，當漏認率較低時，被漏認的邊界節點零散地出現;漏認逐漸增多，邊界節點連續漏認的概率緩慢增高，當超過某個臨界值時，漏認節點形成連續的漏認鏈條的概率急劇增加，在漏認鏈條的中點附近就會出現一個局部極大值點，導致分塊錯誤。由于臨界值高達60%左右，可認為本算法對于邊界漏認有足夠容忍度，能夠應對邊界識別不完整。

3.2 節點部署密度的影響

在第2 節有“均勻”和“各向同性”的假設。當節點部署很密集時，這兩個假設基本成立;如果密度下降，則將背離這兩個假設，后面的分析和設計就有可能不正確。

圖2(h)的平均節點密度是10.2，逐漸降低部署的節點數量。圖5(a)所示的算例平均密度為8.1;(b)所示的算例平均密度為6.4，該密度下部分算例出現多余分塊，拓撲樹的根節點也明顯偏離分塊的中心;(c)所示的算例平均密度為4.4，幾乎所有算例都出現分塊錯誤，拓撲樹根節點也經常不在節點中心。

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

設大量算例中5%的算例出現錯誤的平均密度為密度臨界值，那么仿真實驗表明:密度臨界值在7.1～8.0 之間。

3.3 各種不同的形狀

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

從表1 中可以發現，各算例中的根節點與最優選址之間的平均距離都不到單跳通信距離。這說明本算法中各個根節點可作為網絡融合中心的選址。

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

表1 各算例根節點距離最優選址的平均距離(以單跳通信距離的倍數計)Tab 1 Average distance of the optimal positions of each example rootnodes(counts by multiple of communication distance of single hop)

4 結 論

本文受熱傳導現象的啟發，在WSNs 中模擬熱傳導的過程，通過觀察某時刻的溫度場合溫度梯度，對復雜形狀的WSNs 進行近凸分割，并找到各分塊的中心。

通過仿真實驗，考察了本算法對于不完整邊界識別、低密度網絡以及各種幾何形狀的容忍程度，驗證了算法的適應性和實用性。

［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］ 顧 德，王繼帥.無線傳感器網絡拓撲邊界辨識算法［J］.傳感器與微系統，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.