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

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

無標度無線傳感器網(wǎng)絡的同步

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

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

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

無標度網(wǎng)絡；概率連通；閾值函數(shù)；局部同步；全局同步

0 引言

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

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

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

本文中所有的同步標準與網(wǎng)絡的標度無關，僅與數(shù)據(jù)融合函數(shù)的選取有關。

1 記號及基本概念

記V（k）= ｛i｜i∈Z+｝為時刻k（k≥0）時 WSN的節(jié)點集合，其中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的鄰居節(jié)點集合。集合Ni（k）的勢記作di（k）或者｜Ni（k）｜，這意味著在節(jié)點i的可探測區(qū)域內有di（k）個節(jié)點。假設P｛di（k）=h｝～h-γ，γ是一個常數(shù)并取值于區(qū)間（2，∞）。由文獻［3］可得

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

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

定義1 對于i，z∈V（k），如果存在有限的節(jié)點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）為概率連通圖。

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

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

2 離散型無標度WSN的模型

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

其中，b為常數(shù)。

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

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

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

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

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

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

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

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

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

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

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

3 主要結果

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

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

證明：根據(jù)系統(tǒng)（6）可得

以及題設可得

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

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

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

4 數(shù)值例子和仿真

4.1 例1

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

圖1 由4個節(jié)點組成的概率分支與概率連通圖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之后，節(jié)點2加入到概率分支3，4中，WSN成為概率連通圖（0.06≤k≤20）（如圖1d～f）。取fi（k）=7-k，fiq（k）=7-k/h（k），可0，o=3，4；根據(jù)定理2，WSN達到全局平均同步。仿真結果如圖3所示。

圖2 局部同步Fig.2 Local consensus

5 結論

圖3 全局同步Fig.3 Global consensus

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

［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］牟金平，周武能，王天波，等.無線傳感器網(wǎng)絡在休眠——喚醒機制下的目標同步［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-），男，浙江黃巖人，博士研究生，講師，主要研究方向為傳感器網(wǎng)絡的協(xié)同與控制。

（責任編輯 耿金花）