張瑞華　程合友　梁宇

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

?

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

張瑞華1程合友2梁宇1

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

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

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

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

1事件檢測(cè)算法

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

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

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

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

(1)

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

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

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

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

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

(2)

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

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

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

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

② sink將不完整的權(quán)值網(wǎng)絡(luò)拓?fù)渲朽従又g沒(méi)有權(quán)值的邊補(bǔ)充權(quán)值，得到完整的權(quán)值網(wǎng)絡(luò)拓?fù)?，如圖1(c)所示.因?yàn)榛谧畲罅髯钚「顒澐志W(wǎng)絡(luò)的原理是切割邊的權(quán)值最小，由前面的論述可知，沒(méi)有上傳權(quán)值的區(qū)域不會(huì)是事件邊界，也不是要切割的邊，所以要使權(quán)值盡可能地大，以免影響算法效果.

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

初始化Ti、Si集合.sink掃描生成權(quán)值網(wǎng)絡(luò)拓?fù)洌M(jìn)行最大流最小割算法初始化.因?yàn)樽畲罅髯钚「钏惴ǖ妮斎霝槌跏嫉脑垂?jié)點(diǎn)集合Si、匯節(jié)點(diǎn)集合Ti，因此，必須根據(jù)上傳信息，確定這兩個(gè)集合的初始值.該算法的偽代碼如下所示.

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

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

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

ifWi,j=∞ then

else

endif

? nodei∈A1

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

else

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

end if

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

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

/***尋找所有的相連集合對(duì)***/

? nodei∈Ai

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

Ai、Aj是相連集合對(duì);

end if

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

?相連集合對(duì)(Ai,Aj)

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

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

初始化Si=Ai，Ti=Aj;

else

初始化Si=Aj，Ti=Ai;

end if

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

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

1.4　確定事件區(qū)域

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

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

2仿真實(shí)驗(yàn)

2.1　實(shí)驗(yàn)環(huán)境部署

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

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

2.2　實(shí)驗(yàn)參數(shù)設(shè)置

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

2.2.1參數(shù)C的確定

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

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

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

Table 1　Test results corresponding to different parameter C

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

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

2.2.2參數(shù)?的確定

對(duì)于參數(shù)?，當(dāng)權(quán)值W

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

Table 2　Test results corresponding to different parameter ?

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

2.3　實(shí)驗(yàn)結(jié)果

2.3.1單事件區(qū)域

當(dāng)事件區(qū)域?yàn)閳A形區(qū)域,其半徑為128 m，圓心在(197 m,193 m)，且?0=50，?=800，δ=800，C=0.01時(shí)，檢測(cè)結(jié)果與火災(zāi)事件的相符度，仿真結(jié)果如圖4所示,圖中X、Y分別為坐標(biāo).

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

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

2.3.2多事件區(qū)域

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

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

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

2.2.3檢測(cè)準(zhǔn)確度

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

2.2.4通信量

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

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

3結(jié)論

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

參考文獻(xiàn):

[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ú)線傳感器網(wǎng)絡(luò)中事件區(qū)域檢測(cè)的容錯(cuò)算法 [J].計(jì)算機(jī)學(xué)報(bào)，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)建,楊庚,等.高效容錯(cuò)的無(wú)線傳感網(wǎng)事件及其邊界檢測(cè)算法 [J].計(jì)算機(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ú)線傳感網(wǎng)絡(luò)中的時(shí)空事件檢測(cè)方法 [J].計(jì)算機(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)性分析的事件檢測(cè)算法 [J].計(jì)算機(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.

責(zé)任編輯：牛曉光

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

中圖分類號(hào)：TP393

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

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61202015)；國(guó)家"863"計(jì)劃項(xiàng)目(2013AA013202)

收稿日期：2015-07-15

文章編號(hào)：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)