無標度無線傳感器網絡的同步

牟金平，周武能，王天波，冀 川

（1.東華大學，上海 201620；2.臺州學院，浙江 臨海 317000）

無標度無線傳感器網絡的同步

牟金平1，2，周武能1，王天波1，冀 川1

（1.東華大學，上海 201620；2.臺州學院，浙江 臨海 317000）

研究了離散型無標度無線傳感器網絡（WSN）的同步問題。首先，為了刻畫該網絡在休眠—喚醒機制下變拓撲結構的連通性，給出了概率路徑、概率分支和概率連通等概念。其次，在變拓撲下，給出了一種基于閾值的同步控制協議。假設節點以一定的概率接收到在閾值允許范圍內的數據，在基于閾值的同步控制協議下，WSN達到局部同步或全局同步。最后，數值例子和仿真的結果印證了所得結論的可靠性。

無標度網絡；概率連通；閾值函數；局部同步；全局同步

0 引言

近年來，同步問題吸引著大量的學者去研究［1-2］。但是，其中絕大多數所研究同步問題的是針對標度固定的網絡，而對變標度網絡同步問題的研究甚少。本文就無線傳感器網絡（WSN）的節點在線增加情況下的同步問題進行研究。

在WSN的節點失效之前，當有新節點不停加入時，網絡中有些節點的連接度變大，網絡的標度不斷地增大，WSN可以看作是一種無標度網絡（SFN）。1965年，Solla在文獻［3］中首次提出了SFN的概念。Barabasi和Albert在文［4］中詳細介紹了SFN中節點的連接度服從指數分布。在SFN的框架下，H.Wang和Y.Guo以鞅為工具，以節點的出、入度之間達到平衡為標準研究了離散型SFN的同步問題［5］。

然而，在信號干擾下，無標度數據融合型WSNs的同步問題沒有引起學者們足夠的注意。要解決這一問題，需要考慮兩方面：1）如何處理節點增加時的同步問題？2）如何實現節能？要解決第一個問題，關鍵是所設計的控制器和達到同步的標準應該與網絡的標度相對獨立；解決第二個問題的關鍵是在網絡中實施休眠—喚醒機制（SAM）［6-9］和數據融合［10］。

本文中所有的同步標準與網絡的標度無關，僅與數據融合函數的選取有關。

1 記號及基本概念

記V（k）= ｛i｜i∈Z+｝為時刻k（k≥0）時 WSN的節點集合，其中k=ml，l＞0，m∈Z+且V（k）?V（k+l）。E（k）= ｛（i，j）｜i，j∈V（k）｝為 WSN邊的集合。（i，j）∈E（k）意味著在i與j之間，在時刻k有信息流，并且可能有新的邊加入。從而，非定向 WSN可表示為圖G（k）= ｛V（k），E（k）｝。

記Ni（k）= ｛j｜（i，j）∈E（k）｝為i在時刻k的鄰居節點集合。集合Ni（k）的勢記作di（k）或者｜Ni（k）｜，這意味著在節點i的可探測區域內有di（k）個節點。假設P｛di（k）=h｝～h-γ，γ是一個常數并取值于區間（2，∞）。由文獻［3］可得

在許多應用中，休眠機制（SA）被廣泛應用于節省節點的能量［6-7］。本文中，函數aij（k）表示i與j之間的休眠 —喚 醒行為以及連接權，其中j∈Ni（k）并且aij（k）=aji（k），aij（k）取值為1或0。aij（k）=1表示被喚醒的節點i與j之間有信息流，aij（k）=0表示在i與j之間至少有一個節點進入休眠，從而它們之間暫時無信息流。如果j?Ni（k），那么aij（k）≡0。

為了刻畫在SAM下的拓撲結構，給出下述概念。

定義1 對于i，z∈V（k），如果存在有限的節點i1，…，il∈V（k）使得

其中，0＜p≤1，那么稱在i與z之間有概率路徑，記該路徑為ii1i2…ilz。

定義2 ?i，z∈V′（k）?V（k），如果在i與z之間存在概率路徑，那么稱G′（k）= ｛V′（k），E′（k）｝是圖G（k）的概率連通子圖，其中E′（k）?E（k）。在G（k）中，除了G（k）與G′（k）以外，如果不存在包含G′（k）的概率連通子圖，則稱G′（k）是G（k）的概率連通分支。對于i，z∈V（k），如果在i與z之間存在概率路徑，那么稱G（k）為概率連通圖。

由于每個傳感器的感知和處理數據的能力有限，節點不能感知整個網絡，特別是及時地感知整個網絡的標度。另外，WSN的信息交換圖可能由一些概率分支所組成或者網絡是概率連通的。因此，為了刻畫WSN的拓撲結構，本文給出了概率分支，概率連通等概念。

在不等式（1）中，如果p=1，則上述的概率路徑，概率連通，概率分支等概念與文獻［1］、［5］、［7］和［8］中所指的一樣。

2 離散型無標度WSN的模型

對于i∈V（k），設節點i的狀態為xi（k）∈Rd，d∈Z+。假設i的動態方程為

其中，b為常數。

其中，yj（k）是節點i對節點j狀態測量的結果，yj（k）=xj（k）+rij（k），rij（k）（rij（k）∈Rd）是介于i與j之間的擾動信號，x（k）稱為參考狀態，0＜fi（k）≤1，gi（k）為閥值函數（gi（k）≥0）。

如果yj（k）滿足（4）中的上式的條件，那么i保持與j的連接。否則i暫時斷開與j的連接。采用這種通訊方式的優點是：在節點發送數據之前，每個節點對數據已經作了部分處理，這樣有利于節約節點的能量。

在每個節點的控制項（3）中都含有參考狀態，這種參考狀態可能指每個節點本身連同其所有鄰居節點在內的平均狀態，即

在實際應用中，由于節點數額龐大，WSN的標度往往可以忽略。因此，模型（6）刻畫了每個節點與其鄰居的關系并且模型與整個網絡的標度無關。

假設1 假設P｛aij（k）=1｝=1/（didj），yj（k）滿足：

定義3 在（2）和控制協議（3）下，WSN（6）被稱為無標度數據融合型的網絡。在概率分支G′（k）中，?i∈V′（k），如果

其中，q∈Ni（k），那么稱 WSN（6）達到局部同步。如果

那么稱WSN達到局部平均同步。

在概率連通的 WSN中，?i，q∈V（k），如果式（7）成立，那么稱 WSN（6）達到全局同步。如果式（8）成立，那么稱WSN（6）達到全局平均同步。

在已有相關文獻中，平均同步是指系統中每個節點的狀態達到所有節點狀態的平均值。不同于已有文獻，在無標度WSN中，每個節點只能感知其鄰居節點的狀態，故用局部平均值來刻畫節點所可能達到的狀態。

另外，通常情況下，考慮線性系統的同步問題時，網絡的整個結構以及Laplacian矩陣必須是已知的。本文中，由于WSN的標度是個變量，在分析WSN同步時，將借助于節點的局部結構和相鄰兩個節點之間的狀態誤差。

3 主要結果

先給出下述不等式（9）。

命題1 令Δiq（k+l）=xi（k+l）-xq（k+l），?i∈V′（k）和q∈Ni（k），則有

證明：根據系統（6）可得

以及題設可得

在概率連通的WSNs或者WSNs的概率連通分支中，有下列結果。

那么在控制協議（3）下，模型（6）所表示概率連通分支中的節點達到局部同步。在控制（3）下，如果模型（6）是概率連通的，則模型（6）達到全局同步。

在控制協議（3）中，如果τij（k）=1，θ=1，并且式（1）中的p=1，那么控制協議（3）與文獻［7］中的等式（A1）是一樣的。

4 數值例子和仿真

4.1 例1

考慮由4個節點V（k）= ｛1，2，3，4｝（0＜k≤0.45）組成的 WSN（如圖1a，b，c）所示），其中節點1，2和3，4分別組成兩個概率連通分支。

圖1 由4個節點組成的概率分支與概率連通圖Fig.1 The probability component（show as a，b，c）and the probalility conneated graph（shown as d.e.f）

4.2 例2

假設在k=0.06之前，WSN由兩個概率分支組成（如圖1a～c）。在k=0.06之后，節點2加入到概率分支3，4中，WSN成為概率連通圖（0.06≤k≤20）（如圖1d～f）。取fi（k）=7-k，fiq（k）=7-k/h（k），可0，o=3，4；根據定理2，WSN達到全局平均同步。仿真結果如圖3所示。

圖2 局部同步Fig.2 Local consensus

5 結論

圖3 全局同步Fig.3 Global consensus

本文解決了無標度WSNs的局部和全局同步等問題。假設每個節點都擁有各自的數據融合函數，在通訊中有選擇地與節點交換數據。在協議（3）下，概率分支達到局部同步，概率連通的WSN中達到全局同步。但是，當無標度WSN在時滯環境中運行時，解決其同步問題是一項具有挑戰性的課題，有待進一步研究。

［1］Olfati-Saber R，Murray R M.Consensus problems in networks of agents with switching topology and time-delays［J］.IEEE Transactions on Automatic Control，2004，49（9）：1520-1533.

［2］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless sensor networks：a survey［J］.Computer Networks，2002，38：393-422.

［3］Price D.Networks of scientific papers［J］.Science，1965，149（3683）：510-515.

［4］Barabasi A，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509-512.

［5］Wang H，Guo Y.Consensus on scale-free network［C］∥2008Amercia Control Conference.Westin Seattle Hotel，Seattle，Washington，USA，2008：748-752.

［6］Ye W，Heidemann J，Estrin D.Medium access control with coordinated adaptive sleeping for wireless sensor networks［J］.IEEE/ACM Transations on Networking，2004，12（3）：493-506.

［7］牟金平，周武能，王天波，等.無線傳感器網絡在休眠——喚醒機制下的目標同步［J］.計算機仿真，2012，29（3）：21-24.

Mou Jinping，Zhou Wuneng，Wang Tianbo，et al.Synchronization of wireless sensor networks under the same sleeping awaking method［J］.Computer Simulation，2012，29（3）：21-24.

［8］Zhou W，Mou J，Wang T，et al.Target-synchronization of the distributed wireless sensor networks under the same sleeping-awaking method［J］.Journal of the Franklin Institute，2012，349：2004-2018.

［9］Zhou W N，Mou J P，Wang T B，et al.Quasi-average mean square consensus for wireless sensor networks under three topologies with respect to sleeping-awaking method［J］.Optimal Control Applications and Methods，2013，34（4）：379-395.

［10］Olfati-Saber R，Shamma J S.Consensus filters for sensors networks and distributed sensor fusion［C］//Proceedings of the 44IEEE Conference on Decision and Control，and 2005European Conference.Seville，Spain，2005：6698-6703.

Consensus of Scale Free Wireless Sensor Networks

MOU Jin-ping1，2，ZHOU Wu-neng1，WANG Tian-bo1，JI Chuan1
（1.Donghua University，Shanghai 201620，China；2.Taizhou University，Linhai 317000，China）

In this paper，the consensus problem is investigated for a type of distributed scale-free wireless sensor network（SFWSN）with discrete time case.In order to express the connectivity of the varying topology of SFWSN under sleeping-awaking method，several concepts，such as the probability path，probability component，and probability connected，are proposed.Under the varying topology，a consensus protocol based on the given threshold function is designed.Suppose that every sensor gets the data with a certain probability in the permission range，under the designed protocol，WSN achieves the local consensus or the global consensus.Numerical examples show the reliability of the proposed results.

scale-free networks，probability connection，threshold function，the local consensus，the global consensus

TP301.6；N945.12；TP393

A

1672-3813（2013）03-0061-06

2012-12-04

國家自然科學基金面上項目（61075060）；上海市教委重點項目（12zz064）；臺州學院培育基金（2013PY09）

牟金平（1974-），男，浙江黃巖人，博士研究生，講師，主要研究方向為傳感器網絡的協同與控制。

（責任編輯 耿金花）