基于最大流最小割算法的事件檢測方案*

張瑞華　程合友　梁宇

(1.山東大學 計算機科學與技術(shù)學院， 山東 濟南 250101； 2.山東省輕工集體經(jīng)濟科技信息研究所， 山東 濟南 250014)

?

基于最大流最小割算法的事件檢測方案*

張瑞華1程合友2梁宇1

(1.山東大學 計算機科學與技術(shù)學院， 山東 濟南 250101； 2.山東省輕工集體經(jīng)濟科技信息研究所， 山東 濟南 250014)

摘要：文中把最大流最小割算法應用于無線傳感網(wǎng)絡(luò)的事件檢測中,針對邊沿陡峭的事件，設(shè)計事件區(qū)域檢測算法(G-Cut).該算法首先將相鄰節(jié)點的傳感數(shù)據(jù)轉(zhuǎn)化為權(quán)值，形成流網(wǎng)絡(luò)；利用最大流最小割算法切割流網(wǎng)絡(luò)，獲得事件邊界；再根據(jù)上傳信息隱含的方向，確定事件區(qū)域.以野外火災為例進行仿真實驗，結(jié)果表明：文中算法事件檢測準確度高，節(jié)點計算量低；針對多事件區(qū)域，在不增加節(jié)點計算量和通信量的情況下，仍可保證其檢測準確度.

關(guān)鍵詞：無線傳感網(wǎng)絡(luò)；最大流最小割算法；事件檢測；Boykov新算法；多事件區(qū)域

基于上述問題，文中首次把最大流最小割算法應用于無線傳感網(wǎng)絡(luò)的事件檢測中,針對邊沿陡峭的事件，設(shè)計事件區(qū)域檢測算法G-Cut，該算法將傳感節(jié)點的傳感數(shù)據(jù)轉(zhuǎn)化為鄰居之間的權(quán)值，形成節(jié)點之間的權(quán)值網(wǎng)絡(luò)；利用連通集合相鄰關(guān)系得到最大流最小割算法的初始輸入集合Si、Ti，進而形成流網(wǎng)絡(luò)；采用最大流最小割算法根據(jù)節(jié)點間的權(quán)值劃分流網(wǎng)絡(luò)，將網(wǎng)絡(luò)節(jié)點分成集合So和集合To，得到事件邊界，并根據(jù)上傳信息時隱含的方向確定事件區(qū)域.

1事件檢測算法

事件檢測算法(G-Cut)執(zhí)行過程如圖1所示.圖中ωi表示相連兩節(jié)點的權(quán)值.

圖1　算法實現(xiàn)過程Fig.1　Procedures for realizing the algorithm

1.1　權(quán)值函數(shù)定義

為減少信息傳輸量，當節(jié)點p的傳感數(shù)據(jù)Ip>?0時，才與其鄰居交換信息.其中，?0是有事件發(fā)生時節(jié)點讀數(shù)的閾值，用戶可根據(jù)實際應用環(huán)境預先設(shè)定.節(jié)點獲得鄰居信息后，根據(jù)式(1)計算自己與鄰居之間的權(quán)值Wp,q，該權(quán)值的定義類似文獻[14]的式(7)，即圖像分割時確定像素點差距的函數(shù).

(1)

式中,Wp,q是節(jié)點p和q之間的權(quán)值,κ、C是放大系數(shù),δ是給定的待測環(huán)境變量的最大值,Iq是節(jié)點q的傳感數(shù)據(jù),dist(p,q)是節(jié)點p、q之間的歐式距離.

計算得到的權(quán)值作為最終形成的流網(wǎng)絡(luò)相應邊上的容量.為了利用最大流最小割算法將網(wǎng)絡(luò)從鄰居節(jié)點傳感數(shù)據(jù)差距最大處分開，設(shè)計權(quán)值函數(shù)時，需要保證節(jié)點之間傳感數(shù)據(jù)差距越大得到的權(quán)值越小，系數(shù)κ的存在使計算的權(quán)值是整數(shù).

1.2　權(quán)值網(wǎng)絡(luò)的形成

(1)網(wǎng)絡(luò)初始化.在監(jiān)測區(qū)域均勻布置傳感節(jié)點后，所有節(jié)點泛洪將自身信息(Ni,Xi,Yi)上傳給sink，Ni是節(jié)點i的ID號，(Xi,Yi)是節(jié)點i的坐標.sink節(jié)點根據(jù)接收的信息還原出監(jiān)測區(qū)域內(nèi)節(jié)點布局情況，如圖1(a)所示.隨后網(wǎng)絡(luò)進入監(jiān)測狀態(tài).

(2)節(jié)點信息處理.針對邊沿陡峭的事件，在事件區(qū)域內(nèi)部或無事件發(fā)生的區(qū)域，相鄰節(jié)點傳感數(shù)據(jù)相差不大，其權(quán)值相對較大；在事件邊界兩側(cè)相鄰節(jié)點傳感數(shù)據(jù)變化最大，其權(quán)值相對較小.因此，為減少上傳信息量，節(jié)點只上傳較小的權(quán)值，即當Wp,q

(2)

上傳信息隱含方向的好處是多事件發(fā)生時，sink節(jié)點仍可以根據(jù)節(jié)點上傳的信息確定區(qū)域方向，避免二義性.

節(jié)點信息上傳后，在sink節(jié)點處形成不完整的權(quán)值網(wǎng)絡(luò)，如圖1(b)所示.

(3)sink信息處理.sink節(jié)點根據(jù)上傳信息決策事件的發(fā)生.若沒有收到上傳信息，則沒有事件發(fā)生；否則有事件發(fā)生.若有事件發(fā)生按以下步驟處理：

① sink根據(jù)節(jié)點上傳的信息(Np,Nq,Wp,q)得到最初的并不完整的節(jié)點權(quán)值網(wǎng)絡(luò)拓撲，如圖1(b)所示.

② sink將不完整的權(quán)值網(wǎng)絡(luò)拓撲中鄰居之間沒有權(quán)值的邊補充權(quán)值，得到完整的權(quán)值網(wǎng)絡(luò)拓撲，如圖1(c)所示.因為基于最大流最小割劃分網(wǎng)絡(luò)的原理是切割邊的權(quán)值最小，由前面的論述可知，沒有上傳權(quán)值的區(qū)域不會是事件邊界，也不是要切割的邊，所以要使權(quán)值盡可能地大，以免影響算法效果.

1.3　權(quán)值網(wǎng)絡(luò)轉(zhuǎn)化為流網(wǎng)絡(luò)

初始化Ti、Si集合.sink掃描生成權(quán)值網(wǎng)絡(luò)拓撲，進行最大流最小割算法初始化.因為最大流最小割算法的輸入為初始的源節(jié)點集合Si、匯節(jié)點集合Ti，因此，必須根據(jù)上傳信息，確定這兩個集合的初始值.該算法的偽代碼如下所示.

算法1 initialize()—sink初始化集合Ti,Si.

/***尋找所有的連通區(qū)域***/

掃描生成的權(quán)值網(wǎng)絡(luò),為屏蔽上傳權(quán)值的差異，對于所有的鄰居節(jié)點i和j

ifWi,j=∞ then

else

endif

? nodei∈A1

節(jié)點j加入集合A1;

else

節(jié)點j加入集合B1;

end if

A1節(jié)點所覆蓋的區(qū)域是第1個連通區(qū)域.

重復上述步驟,直到發(fā)現(xiàn)所有的連通區(qū)域A1,A2，…，Ak

/***尋找所有的相連集合對***/

? nodei∈Ai

if ? nodej∈Aj&& nodeiandj是鄰居 then

Ai、Aj是相連集合對;

end if

/*** 初始化集合Si,Ti***/

?相連集合對(Ai,Aj)

掃描集合對所有節(jié)點i,j，i∈Ai&&j∈Aj&& 節(jié)點i、j是鄰居

ifWi,j是節(jié)點i上傳 then

初始化Si=Ai，Ti=Aj;

else

初始化Si=Aj，Ti=Ai;

end if

在該算法中，若只有一個事件區(qū)域，找到兩個連通集合；若有k個事件區(qū)域，則找到k+1個連通集合.如圖1(c)所示，其中外圍16個節(jié)點屬于Ti集合，內(nèi)層9個節(jié)點屬于Si集合.

任意選擇兩個節(jié)點t、s，令t∈Ti,s∈Si，即形成從s到t的流網(wǎng)絡(luò)，直接調(diào)用新最大流最小割算法.

1.4　確定事件區(qū)域

調(diào)用新最大流最小割算法.輸出結(jié)果如圖1(d)所示.此時可以找到事件邊界.根據(jù)上傳信息時隱含的方向確定事件區(qū)域.

最大流最小割算法是圖像分割中應用比較成熟的方法.幾種常用的最大流最小割算法有：Ford-Fulkerson 算法、預流推進算法和Boykov的新算法[14].通過比較，選用Boykov的新算法作為文中G-Cut的基礎(chǔ)算法.

2仿真實驗

2.1　實驗環(huán)境部署

本實驗用Visual Studio 2010 編程模擬仿真，用MATLAB生成圖表，在400 m×400 m的監(jiān)測區(qū)域內(nèi)均勻布置2 500個節(jié)點.利用Manolakos等[15]提出并由Manatakis等經(jīng)真實火災實驗驗證正確的野外火災的一個著火點的溫度場模型，推算出野外火災事件區(qū)域溫度場模型(見圖2)，并依照此模型為傳感器節(jié)點賦初始溫度值.從圖2的模型可以看出，等距離火災溫度變化最大處位于火災邊界，故野外火災屬于邊沿陡峭事件.圖中D表示火災事件中心到外圍的距離.

圖2　二維野外火災事件區(qū)域模型Fig.2　Two-dimensional wildfire event region model

2.2　實驗參數(shù)設(shè)置

由權(quán)值計算公式(1)可知，傳感器部署以后，dist(p,q)已知.δ是火災溫度最大值，根據(jù)火災模型取δ=800 ℃，令κ=1 000.

2.2.1參數(shù)C的確定

當事件區(qū)域是以(197 m,193 m)為圓心，半徑為128 m的圓時，取?=800，根據(jù)W的變化關(guān)系，取不同的參數(shù)C得到不同結(jié)果，如表1所示.

圖3　不同C的權(quán)值W的變化趨勢Fig.3　Function of W under different C

表1不同參數(shù)C下的測試結(jié)果

Table 1　Test results corresponding to different parameter C

檢測準確度計算方法是算法檢測正確的節(jié)點數(shù)除以實際事件區(qū)域節(jié)點數(shù).此事件區(qū)域?qū)嶋H節(jié)點數(shù)為1 263，利用此算法，當C=0.01時，算法檢測到的事件節(jié)點數(shù)為1 217，算法正確檢測的事件節(jié)點數(shù)為1 191，其算法檢測準確率為94.30%.

由圖3可見，對于不同的C值，權(quán)值變化速度不同，仿真環(huán)境d<200，當C=0.01時包含整個權(quán)值變化過程.由表1可以看出，在一定錯誤范圍內(nèi)，C=0.01時，檢測準確率更高.相應地，當d<700范圍內(nèi)時，取C=0.1時包含整個權(quán)值變化過程.實際應用時根據(jù)不同密度取不同的參數(shù)，可使結(jié)果更加準確，C的確定與節(jié)點部署密度、當?shù)鼐唧w氣候等條件有關(guān)，應根據(jù)具體情況取合理值.根據(jù)仿真實驗部署環(huán)境，本實驗取C=0.01.

2.2.2參數(shù)?的確定

對于參數(shù)?，當權(quán)值W

表2不同參數(shù)?下的測試結(jié)果

Table 2　Test results corresponding to different parameter ?

由表2可以看出，上傳節(jié)點個數(shù)隨?的增大而增加.這是由于?增大，可上傳的權(quán)值數(shù)量隨之增加，檢測的準確率也略有增加.因此在實際應用中，可以根據(jù)使用者對誤差的容忍程度選擇合適的?值，從而節(jié)約能量.

2.3　實驗結(jié)果

2.3.1單事件區(qū)域

當事件區(qū)域為圓形區(qū)域,其半徑為128 m，圓心在(197 m,193 m)，且?0=50，?=800，δ=800，C=0.01時，檢測結(jié)果與火災事件的相符度，仿真結(jié)果如圖4所示,圖中X、Y分別為坐標.

圖4中，“*”區(qū)域是失判區(qū)域，即算法沒有檢測到的真實事件區(qū)域，“+”區(qū)域是誤判區(qū)域，即算法檢測錯誤的區(qū)域，“小方框”區(qū)域是算法檢測正確的區(qū)域.從圖中可以看出所得到的仿真結(jié)果與原始事件區(qū)域略有偏差.之所以會產(chǎn)生一定的誤差是由于本算法基于最大流最小割，其工作原理是根據(jù)節(jié)點間權(quán)值切割網(wǎng)絡(luò)，理論上切割的區(qū)域應為火災邊界溫度變化最快的點連接而成的區(qū)域，而實際實施過程中，節(jié)點為離散分布，僅用兩點間的權(quán)值模擬火災溫度變化趨勢，所得結(jié)果可能為溫度變化最快點附近ξ范圍內(nèi)某一點，因此實際結(jié)果會與理論分析有一定誤差.

圖4　單事件的仿真結(jié)果Fig.4　Simulation results of a single event region

2.3.2多事件區(qū)域

本算法對于多個事件區(qū)域，可在不增加計算量的前提下，避免二義性，保證準確性.當事件區(qū)域為兩個半徑為64 m時圓心分別在(117 m,113 m)和(293 m,290 m)的圓形區(qū)域，且設(shè)置相同的參數(shù)時，其仿真結(jié)果如圖5所示.

圖5中，“*”區(qū)域是失判區(qū)域，“+”是誤判區(qū)域，“小方框”是算法檢測正確的區(qū)域.因為該算法利用連通集合相鄰關(guān)系得到初始化集合T、S時，無論幾個事件區(qū)域，事件內(nèi)部的節(jié)點都已經(jīng)包含在S或T內(nèi)，調(diào)用新最大流最小割算法可找到事件邊界.再利用上傳信息時隱含的傳感數(shù)據(jù)大小關(guān)系，可以判定T和S究竟哪個是事件區(qū)域，因此，本算法對于多個事件區(qū)域，仍可以在不增加計算量的前提下保證準確性.

圖5　多事件的仿真結(jié)果Fig.5　Simulation results of a multi-event region

2.2.3檢測準確度

取不同的事件區(qū)域大小，經(jīng)50次統(tǒng)計平均，檢測準確度分別為：86.4%(Iso-Map)、92.6%(G-Cut)、94.1%(TinyDB).本算法G-Cut的準確度在TinyDB[11]和Iso-Map[12]算法之間.因為TinyDB算法上傳所有節(jié)點的信息，只在形成等值線圖時有一些誤差；Iso-Map算法上傳關(guān)鍵點的信息，誤差相對較大；本算法G-Cut上傳事件邊界一定寬度范圍內(nèi)鄰居間的權(quán)值，在權(quán)值網(wǎng)絡(luò)劃分時會有一定偏差.

2.2.4通信量

在保證準確性的前提下，本算法G-Cut的通信量介于TinyDB和Iso-Map算法之間，其通信量α與歸一化節(jié)點密度β之間的關(guān)系如圖6所示.因為TinyDB是上傳所有信息，所以隨著節(jié)點密度增加，通信量增大.Iso-Map上傳關(guān)鍵點的信息，因此通信量不隨節(jié)點密度增加而增大.文中的G-Cut算法上傳邊界一定寬度范圍內(nèi)的權(quán)值，因此會比TinyDB通信量少，但比Iso-Map多，且隨節(jié)點密度增加而增大.

圖6　通信量與節(jié)點密度的關(guān)系Fig.6　Relationship between the communication traffic amount and the density of nodes

3結(jié)論

針對某類邊沿陡峭的事件檢測，文中設(shè)計了一種基于最大流最小割算法的事件檢測方案.基于野外火災模型的仿真實驗表明，最大流最小割算法用于檢測無線傳感網(wǎng)絡(luò)事件時，與基于等值線圖的事件檢測算法相比檢測準確度高，通信量略有增加；可直接找到事件邊界再根據(jù)上傳信息時隱含的方向判定事件區(qū)域，不需要模式匹配，解決了事件模型不易確定的難題；用于多事件區(qū)域時仍可保證其準確性，且不需要增加計算量.

參考文獻:

[1]CHEN Dan,LIU Zhixin,WANG Lizhe.Natural disaster monitoring with wireless sensor networks：a case study of data-intensive applications upon low-cost scalable systems [J].Mobile Networks and Applications,2013,18(5)：651-663.

[2]BENKHELIFA Imane,NOUALI-TABOUDJEMAT Nadia,MOUSSAOUI Samira.Disaster management projects using wireless sensor networks：an overview [C]∥ Proceedings of the 28th International Conference on Advanced Information Networking and Applications Workshops.Victoria：IEEE,2014：605-610.

[3]XU Guobao,SHEN Weiming,WANG Xianbin.Applications of wireless sensor networks in marine environment monitoring：a survey [J].Sensors,2014,14(9):16932-16954.

[4]MARCHENKO Nikolaj,ANDRE Torsten,BRANDNER Guenther.An experimental study of selective cooperative relaying in industrial wireless sensor networks [J]. IEEE Transactions on Industrial Informatics,2014,10(3)：1806-1816.

[5]ZHENG Yujiao,CAO Nianxia,THAKSHILA Wimalajeewa.Compressive sensing based probabilistic sensor management for target tracking in wireless sensor networks [J].IEEE Transactions on Signal Processing,2015,63(22)：6049-6060.

[6]ZHANG Fan,CHEN Jiming,LI Hongbin,et al.Distributed active sensor scheduling for target tracking in ultrasonic sensor networks [J].Mobile Networks and Applications,2012,17(5)：582-593.

[7]曹冬磊，曹建農(nóng)，金蓓弘.一種無線傳感器網(wǎng)絡(luò)中事件區(qū)域檢測的容錯算法 [J].計算機學報，2007,30(10)：1770-1776.

CAO Dong-Lei,CAO Jian-nong,JIN Bei-hong.A fault-tolerant algorithm for event region detection in wireless sensor networks [J].Chinese Journal of Computers,2007,30(10)：1770-1776.

[8]徐小龍,耿衛(wèi)建,楊庚,等.高效容錯的無線傳感網(wǎng)事件及其邊界檢測算法 [J].計算機研究與發(fā)展,2014,51(5):997-1008.

XU Xiao-long,GENG Wei-jian,YANG Geng，et al.An efficient fault-tolerant event and event boundary detection algorithm for wireless sensor networks [J].Journal of Computer Research and Development,2014,51(5):997-1008.

[9]鄭志平，胡圣波，舒恒.一種無線傳感網(wǎng)絡(luò)中的時空事件檢測方法 [J].計算機仿真,2010,27(8):114-117.

ZHENG Zhi-ping,HU Sheng-bo,SHU Heng.A spatio tanporal event detection approach for wireless sensor network [J].Computer Simulation,2010,27(8):114-117.

[10]石勝飛,張偉,李建中.一種基于模式匹配與相關(guān)性分析的事件檢測算法 [J].計算機研究與發(fā)展,2014,51(8):1871-1879.

SHI Sheng-fei,ZHANG Wei,LI Jian-zhong.A complex event detection algorithm based on correlation analysis [J].Journal of Computer Research and Development,2014,51(8):1871-1879.

[11]JOSEPH M Hellerstein,WEI Hong,SAMUEL Madden,et al.Beyond average：toward sophisticated sensing with queries [C]∥Proceedings of IEEE/ACM Information Processing in Sensor Networks(IPSN).Palo Alto：IEEE/ACM,2003:1-16.

[12]LI Mo,LIU Yunhao.Iso-Map：energy efficient contour mapping in wireless sensor networks [J].IEEE Transactions on Knowledge and Data Engineering,2010,22(5)：699-710.

[13]DRAGANA Bajovic,BRUNO Sinopoli,JOAO Xavier.Sensor selection for event detection in wireless sensor networks [J].IEEE Transactions on Signal Processing,2011,59(10)：4938-4953.

[14]BOYKOV Yuri,FUNKA-LEA Gareth.Graph cuts and efficient N-D image segmentation [J].International Journal of Computer Vision,2006,70(2):109-131.

[15]MANOLAKOS E S,MANATAKIS D V,XANTHOPOULOS G.Temperature field modeling and simulation of wireless sensor network behavior during a spreading wildfire [C]∥Proceedings of the 16th European Signal Processing Conference.Lausanne：IEEE,2008:1-5.

責任編輯：牛曉光

Event Detection Scheme Based on Max-Flow/Min-Cut Algorithm

ZHANGRui-hua1CHENGHe-you2LIANGYu1

(1. School of Computer Science and Technology, Shandong University, Jinan 250101, Shandong, China；

2. Shandong Light Industry Collective Economy Science and Technology Information Institute, Jinan 250014, Shandong, China)

Abstract:In this paper, the max-flow/min-cut algorithm is applied to the event detection in wireless sensor networks, and an event detection algorithm (G-Cut) is proposed for boundary-abrupt events. In the algorithm, firstly, the sensing data of adjacent nodes are transformed into weight values, and thus a flow network is formed. Then, the event boundary is obtained by using the max-flow/min-cut algorithm to cut the flow network. Finally, the event area is determined according to the direction implied in upload information. Simulation results on wildfire events show that the proposed algorithm achieves a high accuracy of event detection with a small computation amount of nodes, and for multi-event regions, it can guarantee the detection accuracy without increasing the computation amount and traffic of nodes.

Key words:wireless sensor networks; max-flow/min-cut algorithm; event detection; Boykov new algorithm; multi-event region

doi：10.3969/j.issn.1000-565X.2016.01.020

中圖分類號：TP393

作者簡介：張瑞華(1969-)，女，博士，副教授，主要從事無線傳感器網(wǎng)絡(luò)研究.E-mail：ruihua_zhang@sdu.edu.cn

*基金項目：國家自然科學基金資助項目(61202015)；國家"863"計劃項目(2013AA013202)

收稿日期：2015-07-15

文章編號：1000-565X(2016)01- 0139- 06

Foundation items： Supported by the National Natural Science Foundation of China(61202015)and the National High-tech R&D Program of China(863 Program)(2013AA013202)