無(wú)標(biāo)度無(wú)線傳感器網(wǎng)絡(luò)的同步

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

（1.東華大學(xué)，上海 201620；2.臺(tái)州學(xué)院，浙江 臨海 317000）

無(wú)標(biāo)度無(wú)線傳感器網(wǎng)絡(luò)的同步

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

（1.東華大學(xué)，上海 201620；2.臺(tái)州學(xué)院，浙江 臨海 317000）

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

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

0 引言

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

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

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

本文中所有的同步標(biāo)準(zhǔn)與網(wǎng)絡(luò)的標(biāo)度無(wú)關(guān)，僅與數(shù)據(jù)融合函數(shù)的選取有關(guān)。

1 記號(hào)及基本概念

記V（k）= ｛i｜i∈Z+｝為時(shí)刻k（k≥0）時(shí) WSN的節(jié)點(diǎn)集合，其中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之間，在時(shí)刻k有信息流，并且可能有新的邊加入。從而，非定向 WSN可表示為圖G（k）= ｛V（k），E（k）｝。

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

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

為了刻畫(huà)在SAM下的拓?fù)浣Y(jié)構(gòu)，給出下述概念。

定義1 對(duì)于i，z∈V（k），如果存在有限的節(jié)點(diǎn)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）的概率連通分支。對(duì)于i，z∈V（k），如果在i與z之間存在概率路徑，那么稱G（k）為概率連通圖。

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

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

2 離散型無(wú)標(biāo)度WSN的模型

對(duì)于i∈V（k），設(shè)節(jié)點(diǎn)i的狀態(tài)為xi（k）∈Rd，d∈Z+。假設(shè)i的動(dòng)態(tài)方程為

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

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

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

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

在實(shí)際應(yīng)用中，由于節(jié)點(diǎn)數(shù)額龐大，WSN的標(biāo)度往往可以忽略。因此，模型（6）刻畫(huà)了每個(gè)節(jié)點(diǎn)與其鄰居的關(guān)系并且模型與整個(gè)網(wǎng)絡(luò)的標(biāo)度無(wú)關(guān)。

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

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

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

那么稱WSN達(dá)到局部平均同步。

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

在已有相關(guān)文獻(xiàn)中，平均同步是指系統(tǒng)中每個(gè)節(jié)點(diǎn)的狀態(tài)達(dá)到所有節(jié)點(diǎn)狀態(tài)的平均值。不同于已有文獻(xiàn)，在無(wú)標(biāo)度WSN中，每個(gè)節(jié)點(diǎn)只能感知其鄰居節(jié)點(diǎn)的狀態(tài)，故用局部平均值來(lái)刻畫(huà)節(jié)點(diǎn)所可能達(dá)到的狀態(tài)。

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

3 主要結(jié)果

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

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

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

以及題設(shè)可得

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

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

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

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

4.1 例1

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

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

4.2 例2

假設(shè)在k=0.06之前，WSN由兩個(gè)概率分支組成（如圖1a～c）。在k=0.06之后，節(jié)點(diǎn)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達(dá)到全局平均同步。仿真結(jié)果如圖3所示。

圖2 局部同步Fig.2 Local consensus

5 結(jié)論

圖3 全局同步Fig.3 Global consensus

本文解決了無(wú)標(biāo)度WSNs的局部和全局同步等問(wèn)題。假設(shè)每個(gè)節(jié)點(diǎn)都擁有各自的數(shù)據(jù)融合函數(shù)，在通訊中有選擇地與節(jié)點(diǎn)交換數(shù)據(jù)。在協(xié)議（3）下，概率分支達(dá)到局部同步，概率連通的WSN中達(dá)到全局同步。但是，當(dāng)無(wú)標(biāo)度WSN在時(shí)滯環(huán)境中運(yùn)行時(shí)，解決其同步問(wèn)題是一項(xiàng)具有挑戰(zhàn)性的課題，有待進(jì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ú)線傳感器網(wǎng)絡(luò)在休眠——喚醒機(jī)制下的目標(biāo)同步［J］.計(jì)算機(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

國(guó)家自然科學(xué)基金面上項(xiàng)目（61075060）；上海市教委重點(diǎn)項(xiàng)目（12zz064）；臺(tái)州學(xué)院培育基金（2013PY09）

牟金平（1974-），男，浙江黃巖人，博士研究生，講師，主要研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)的協(xié)同與控制。

（責(zé)任編輯 耿金花）