無(wú)線傳感網(wǎng)中基于信息增益最大化的泛在數(shù)據(jù)收集算法

宋三華

(黃淮學(xué)院 信息工程學(xué)院，河南駐馬店 463000)

無(wú)線傳感網(wǎng)中基于信息增益最大化的泛在數(shù)據(jù)收集算法

宋三華

(黃淮學(xué)院 信息工程學(xué)院，河南駐馬店 463000)

基于移動(dòng)設(shè)備的泛在數(shù)據(jù)收集是目前的研究熱點(diǎn)。然而現(xiàn)有的數(shù)據(jù)收集方案關(guān)注的重點(diǎn)是提高數(shù)據(jù)收集的可靠性和能效，很少考慮傳感器數(shù)據(jù)攜帶的信息價(jià)值。此外，移動(dòng)用戶可能沒(méi)有足夠多的時(shí)間收集周圍傳感器的所有數(shù)據(jù)。因此，有必要收集對(duì)于用戶來(lái)說(shuō)價(jià)值最大的數(shù)據(jù)。本文提出一種基于信息增益最大化的泛在數(shù)據(jù)收集算法。該算法首先利用移動(dòng)設(shè)備可用容量估計(jì)值和傳感器需求來(lái)自動(dòng)確定數(shù)據(jù)收集樹(shù)構(gòu)建的最大層數(shù)，然后通過(guò)數(shù)據(jù)收集樹(shù)的遷移來(lái)支持移動(dòng)用戶在自身移動(dòng)性不受限制的條件下進(jìn)行分布式數(shù)據(jù)收集。此外，移動(dòng)用戶可以根據(jù)自身速度，動(dòng)態(tài)估計(jì)可以用于數(shù)據(jù)收集的設(shè)備容量。仿真實(shí)驗(yàn)結(jié)果表明，與當(dāng)前最新的其他算法相比，本文算法可將信息價(jià)值提高50%、能耗降低50%。

移動(dòng)設(shè)備；無(wú)線傳感器網(wǎng)絡(luò)；泛在數(shù)據(jù)收集；信息增益

0 引 言

隨著移動(dòng)設(shè)備的發(fā)展，泛在數(shù)據(jù)收集[1]使得用戶利用他們的移動(dòng)設(shè)備(比如PDA或者智能手機(jī))從周圍的傳感器收集數(shù)據(jù)。這種架構(gòu)增加了無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSN)部署的靈活性，為傳感器數(shù)據(jù)收集提供了一種高性價(jià)比解決方案[2,3]。與傳統(tǒng)的WSN不同，泛在數(shù)據(jù)收集不需要依靠固定式Sink收集整個(gè)網(wǎng)絡(luò)的傳感器數(shù)據(jù)，而是利用移動(dòng)設(shè)備從周圍傳感器中進(jìn)行泛在收集數(shù)據(jù)。移動(dòng)用戶的移動(dòng)性不受限制，無(wú)線通信范圍有限，給泛在數(shù)據(jù)收集帶來(lái)了挑戰(zhàn)。具體來(lái)說(shuō)，考慮到移動(dòng)用戶可能連續(xù)不斷的快速移動(dòng)，移動(dòng)設(shè)備和傳感器間的通信時(shí)間非常短。如何保證移動(dòng)用戶在有限的通信時(shí)間和無(wú)線容量下實(shí)現(xiàn)數(shù)據(jù)收集的信息增益最大化具有重要意義[4,5]。

Gu等人[6]提出一種基于分區(qū)的數(shù)據(jù)收集算法，通過(guò)對(duì)移動(dòng)設(shè)備的運(yùn)動(dòng)進(jìn)行調(diào)度，盡量降低了對(duì)移動(dòng)速度的要求，避免了緩存溢出。Bisnik等人[7]研究了基于移動(dòng)傳感器的質(zhì)量覆蓋問(wèn)題，分析了受控移動(dòng)性對(duì)事件收集比例的影響。Xu等人[8]進(jìn)一步研究了帶有移動(dòng)Sink的傳感器網(wǎng)絡(luò)延時(shí)容忍事件收集問(wèn)題，考慮了事件在傳感區(qū)域中的時(shí)空關(guān)聯(lián)。He等人[9]從理論角度分析了數(shù)據(jù)收集的性能，利用一種排隊(duì)模型評(píng)估了移動(dòng)設(shè)備的服務(wù)準(zhǔn)則。然而，上述研究均限制了數(shù)據(jù)收集時(shí)移動(dòng)Sink的移動(dòng)性，而本文中的移動(dòng)用戶為獨(dú)立用戶，其移動(dòng)性不受限制。

另外還有，Kusy等人[10]提出一種算法利用訓(xùn)練數(shù)據(jù)來(lái)預(yù)測(cè)移動(dòng)Sink的移動(dòng)模式。他們計(jì)算并維護(hù)移動(dòng)Sink的移動(dòng)性圖，以提升數(shù)據(jù)收集時(shí)的路由可靠性。類似地，Lee等人[11]提出一種路由算法，通過(guò)利用移動(dòng)Sink的移動(dòng)模式來(lái)盡量降低能耗和網(wǎng)絡(luò)擁塞。Li等人[12]提出一種泛在數(shù)據(jù)收集算法λ-Flooding。該算法首先基于泛洪機(jī)制來(lái)構(gòu)建數(shù)據(jù)收集樹(shù)，然后在本地進(jìn)行數(shù)據(jù)收集樹(shù)的更新。然而總的來(lái)說(shuō)，以上研究工作的重點(diǎn)是提高數(shù)據(jù)收集的可靠性和能效，他們沒(méi)有考慮無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集時(shí)傳感器數(shù)據(jù)攜帶的信息價(jià)值。此外，移動(dòng)用戶可能沒(méi)有足夠多的時(shí)間收集周圍傳感器的所有數(shù)據(jù)。因此，有必要收集對(duì)于用戶來(lái)說(shuō)價(jià)值最大的數(shù)據(jù)。本文提出一種分布式數(shù)據(jù)收集算法，通過(guò)對(duì)數(shù)據(jù)收集進(jìn)行調(diào)度來(lái)實(shí)現(xiàn)數(shù)據(jù)收集信息增益的最大化?？偟膩?lái)說(shuō)，本文主要貢獻(xiàn)如下：首先，提出一種分布式數(shù)據(jù)收集算法EQRoute，實(shí)現(xiàn)移動(dòng)用戶基于信息價(jià)值的泛在數(shù)據(jù)收集。該算法支持移動(dòng)用戶在自身移動(dòng)性不受限制的條件下進(jìn)行分布式數(shù)據(jù)收集。其次，移動(dòng)用戶可以根據(jù)自身速度，動(dòng)態(tài)估計(jì)可以用于數(shù)據(jù)收集的設(shè)備容量。最后，通過(guò)全面的仿真實(shí)驗(yàn)評(píng)估了EQRoute算法的性能。與當(dāng)前最先進(jìn)的其他算法相比，本文算法提高了數(shù)據(jù)收集時(shí)的信息價(jià)值，顯著降低了能耗。

1 系統(tǒng)模型

1.1 應(yīng)用場(chǎng)景

考慮圖1所示的傳感器監(jiān)測(cè)區(qū)域，一個(gè)移動(dòng)用戶為了收集數(shù)據(jù)(比如溫度，環(huán)境污染情況)而在傳感區(qū)域中行走。監(jiān)測(cè)區(qū)域中的傳感器周期性地獲得傳感器測(cè)量值，并將其存儲(chǔ)在緩存中。移動(dòng)用戶經(jīng)過(guò)傳感器時(shí)可以收集這些數(shù)據(jù)。本文利用信息價(jià)值來(lái)表示傳感數(shù)據(jù)攜帶的各種觀測(cè)值的重要性[13]。它經(jīng)過(guò)正規(guī)化后范圍在0到1之間，即w=[0,1]。一般而言，移動(dòng)用戶希望收集可使他們的信息價(jià)值最大的數(shù)據(jù)。例如。在圖1中，如果用戶用于數(shù)據(jù)收集的容量有限，則該移動(dòng)用戶將收集w=0.8而不是w=0.1的數(shù)據(jù)。圖中的數(shù)字表示傳感數(shù)據(jù)的信息價(jià)值。為了使信息增益最大化，信息價(jià)值大的數(shù)據(jù)在數(shù)據(jù)收集時(shí)具有較高的優(yōu)先級(jí)。

圖1 應(yīng)用場(chǎng)景實(shí)例

1.2 挑戰(zhàn)和設(shè)計(jì)目標(biāo)

手機(jī)和無(wú)線傳感器只有互相位于對(duì)方通信范圍內(nèi)時(shí)，二者才有機(jī)會(huì)通信。因此，如果移動(dòng)用戶在運(yùn)動(dòng)時(shí)移動(dòng)性不受限制且難以預(yù)測(cè)，則收集無(wú)線傳感器數(shù)據(jù)的難度很大。考慮到無(wú)線通信距離的有限性，比如IEEE 802.15.4或藍(lán)牙標(biāo)準(zhǔn)明確的通信距離，當(dāng)移動(dòng)用戶快速連續(xù)移動(dòng)時(shí)，用于數(shù)據(jù)收集的通信時(shí)間很短。因?yàn)閭鞲衅骱鸵苿?dòng)設(shè)備在相同的無(wú)線信道上通信，它們必須與周圍的節(jié)點(diǎn)共享有限的無(wú)線容量。移動(dòng)節(jié)點(diǎn)是接收并處理大量數(shù)據(jù)的數(shù)據(jù)收集樹(shù)的根節(jié)點(diǎn)，所以移動(dòng)節(jié)點(diǎn)很可能成為性能瓶頸。鑒于上述原因，移動(dòng)用戶有必要收集可使總體信息價(jià)值最大的數(shù)據(jù)，從而在保證數(shù)據(jù)收集質(zhì)量的前提下，降低通信開(kāi)銷。為此，本文設(shè)計(jì)的泛在數(shù)據(jù)收集的目標(biāo)是：(1)它支持基于信息價(jià)值的泛在數(shù)據(jù)收集，實(shí)現(xiàn)收集數(shù)據(jù)的信息價(jià)值最大化，且能耗較低。(2) 能根據(jù)移動(dòng)用戶的移動(dòng)速度情況，提高數(shù)據(jù)收集的可靠性。(3)可采取分布式策略，對(duì)多個(gè)移動(dòng)用戶的數(shù)據(jù)收集進(jìn)行協(xié)調(diào)。

2 基于信息價(jià)值的泛在數(shù)據(jù)收集

在數(shù)據(jù)收集過(guò)程中，傳感器節(jié)點(diǎn)周期性地生成傳感數(shù)據(jù)，并將數(shù)據(jù)緩存。支持兼容性無(wú)線組件的移動(dòng)設(shè)備，比如IEEE 802.15.4或藍(lán)牙設(shè)備，可從周圍傳感器中收集數(shù)據(jù)。以后連接互聯(lián)網(wǎng)時(shí)，移動(dòng)設(shè)備可將收集到的數(shù)據(jù)上載到服務(wù)器上。本文重點(diǎn)研究從無(wú)線傳感器到移動(dòng)用戶的數(shù)據(jù)收集問(wèn)題。我們的目標(biāo)是實(shí)現(xiàn)信息價(jià)值的最大化，降低泛在數(shù)據(jù)收集的通信開(kāi)銷。移動(dòng)用戶模擬為一個(gè)移動(dòng)性不受限制、通信范圍有限、移動(dòng)速度可變的移動(dòng)單元(ME)。傳感器只要位于移動(dòng)單元的無(wú)線通信范圍內(nèi)，就可以與移動(dòng)單元通信。將數(shù)據(jù)從無(wú)線傳感器傳輸?shù)揭苿?dòng)用戶時(shí)，可以采用多跳路由。

2.1 問(wèn)題描述

(1)

(2)

(3)

(4)

其中，ui=wi/cij表示一個(gè)數(shù)據(jù)報(bào)文di每單位通信成本的信息增益，即收集數(shù)據(jù)的信息價(jià)值除以通信成本跳數(shù)。本文研究問(wèn)題的目標(biāo)函數(shù)是使所有收集數(shù)據(jù)的ui之和U最大化。約束2可保證每個(gè)報(bào)文di只被傳輸給一個(gè)移動(dòng)用戶。約束3允許一個(gè)報(bào)文中傳輸部分?jǐn)?shù)據(jù)。約束4保證在一個(gè)給定時(shí)隙中，移動(dòng)用戶j接收到的所有報(bào)文不超過(guò)它的容量Cj。

2.2 集中式最優(yōu)算法

算法1：集中式容量分配1：Cj：移動(dòng)用戶j的容量；2：wi：數(shù)據(jù)di的信息價(jià)值；3：cij：di到達(dá)j的跳數(shù)；4：5：移動(dòng)用戶j對(duì)網(wǎng)絡(luò)中的所有傳感器廣播數(shù)據(jù)；6：每個(gè)傳感器向j做出回應(yīng)，回應(yīng)數(shù)據(jù)的價(jià)值為wi，跳數(shù)為cij；7：whileCj>0do8： 選擇可使wi/cij最大的di；9： ifCj>1then10： xij=1；11： else12： xij=Cj；13： endif14： Cj=Cj-xij；15：endwhile

定理1:上述貪婪算法可為傳感器數(shù)據(jù)收集中的容量分配問(wèn)題提供最優(yōu)解。

證明：該算法為了接收傳感器數(shù)據(jù)，將容量Cj全部分配完。假設(shè)容量有限，因此容量不足以收集網(wǎng)絡(luò)中的所有數(shù)據(jù)。即存在一個(gè)q，使1=x1=…=xq-1>xq>xq+1=…=0，其中xn+1=0。通過(guò)與該問(wèn)題其他解y1,…,yn做比較可證明算法1的解的最優(yōu)性。因?yàn)閷?duì)所有i，wi/cij均為正，如果∑iyi=Cj，則只有該解為最優(yōu)解。用k表示可使yk<1的最小索引，用l表示可使yl>0且k0，將yk增加∈，yl減小，這樣處理之后獲得一個(gè)可行解，其價(jià)值不小于解y1,…,yn的價(jià)值。此外，要么yk等于1，或者yl等于0。重復(fù)上述推理，最終可以獲得貪婪算法生成的解。證畢。

然而，該算法的工作模式為集中式模式。如上文所述，移動(dòng)用戶必須向整個(gè)網(wǎng)絡(luò)注入數(shù)據(jù)，或者通過(guò)h跳傳輸進(jìn)行廣播，但是h難以確定。另外，上述集中式算法的能耗也較高。移動(dòng)用戶必須等待來(lái)自所有傳感器的數(shù)據(jù)，然后才能向各個(gè)傳感器分配容量，其通信開(kāi)銷的數(shù)量級(jí)是O(N)，其中N表示網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量。

3 分布式算法設(shè)計(jì)

本節(jié)提出一種基于信息增益最大化的分布式泛在數(shù)據(jù)收集算法EQRoute。其主要思路是利用可用容量估計(jì)值Cj和傳感器需求來(lái)自動(dòng)確定數(shù)據(jù)收集樹(shù)構(gòu)建的最大層數(shù)。分布式設(shè)計(jì)也支持多個(gè)移動(dòng)用戶間進(jìn)行數(shù)據(jù)收集協(xié)作。下面從兩個(gè)方面給出本文分布式算法：數(shù)據(jù)收集樹(shù)的構(gòu)建，數(shù)據(jù)收集樹(shù)的遷移。

3.1 數(shù)據(jù)收集樹(shù)的構(gòu)建

假設(shè)每個(gè)傳感器生成高優(yōu)先級(jí)數(shù)據(jù)和低優(yōu)先級(jí)數(shù)據(jù)的概率分別為pH和pL，且pH+pL=1。它們的信息價(jià)值表示為wH和wL，且wH>wL。與大部分研究類似，在開(kāi)始構(gòu)建數(shù)據(jù)收集樹(shù)時(shí)移動(dòng)用戶需要發(fā)送HELLO報(bào)文。然而，與算法1不同，我們沒(méi)有向網(wǎng)絡(luò)注入大量數(shù)據(jù)，或者廣播預(yù)先確定的跳數(shù)，而是采取分布式策略，讓每個(gè)節(jié)點(diǎn)檢查其剩余容量，然后決定是否將樹(shù)擴(kuò)展到下一層。

(5)

其中，μj表示服務(wù)率，vj表示j的移動(dòng)速度。移動(dòng)用戶j不斷地根據(jù)其移動(dòng)速度來(lái)估計(jì)自己的可用容量。本文通過(guò)運(yùn)行CapacityAllocation(j,Cj)算法(算法2)來(lái)啟動(dòng)數(shù)據(jù)收集流程。

算法2：分布式容量分配1：dHi：節(jié)點(diǎn)i高優(yōu)先級(jí)數(shù)據(jù)所需要的容量；2：dLi：節(jié)點(diǎn)i低優(yōu)先級(jí)數(shù)據(jù)所需要的容量；3：fj：節(jié)點(diǎn)j的自由容量；開(kāi)始時(shí)fj=Cj；4：5：ProcedureCapacityAllocation(j，fj)6：向所有單跳相鄰節(jié)點(diǎn)廣播HELLO信息；7：每個(gè)相鄰節(jié)點(diǎn)i按照參數(shù)dHi和dLi做出回復(fù)； {//為數(shù)據(jù)H分配容量}8：for相鄰節(jié)點(diǎn)i的每個(gè)回復(fù)do9： iffj+dLj>0then10： 為dHi分配容量；11： fj=fj-min(fj+dLj，dHi)；12： endif13：endfor {//為數(shù)據(jù)L分配容量}14：for每個(gè)dLido15：iffj>0then16： 為dLi分配容量；17： fj=fj-min(fj，dLi)；18： endif19：在endfor20：根據(jù)fi=fj/N(j)，為每個(gè)i分配剩余容量； {//擴(kuò)展樹(shù)}21：for每個(gè)相鄰節(jié)點(diǎn)ido22： iffi>0then23： RunCapacityAllocate(i，fi)；24： endif25：endfor endProcedure

3.2 數(shù)據(jù)收集樹(shù)的遷移

如上文所示，每經(jīng)過(guò)時(shí)間Δt，移動(dòng)用戶便估計(jì)數(shù)據(jù)收集樹(shù)的新容量。然而，由于移動(dòng)用戶移動(dòng)速度和方向可能發(fā)生變化，移動(dòng)用戶和傳感器間的通信仍然可能終止。因此，移動(dòng)用戶周期性地向相鄰節(jié)點(diǎn)廣播“MobileHere”維護(hù)報(bào)文，以通知相鄰節(jié)點(diǎn)它仍然存在?？傮w來(lái)說(shuō)，傳感器被動(dòng)等待維護(hù)報(bào)文。然而，如果沒(méi)有接收到任何維護(hù)報(bào)文，則傳感器也可以主動(dòng)檢測(cè)移動(dòng)用戶的存在情況。

此外，可以根據(jù)移動(dòng)用戶的新位置，利用MobileHere報(bào)文來(lái)更新樹(shù)結(jié)構(gòu)。例如，節(jié)點(diǎn)i如果直接接收到移動(dòng)用戶的維護(hù)報(bào)文，則可認(rèn)為移動(dòng)用戶與它距離很近。節(jié)點(diǎn)i可以直接與移動(dòng)用戶通信，而不用通過(guò)中繼節(jié)點(diǎn)采用更長(zhǎng)的路徑。利用樹(shù)遷移策略便可處理這種情況。為了便于闡述，本文將遷移過(guò)程分為兩種：內(nèi)部樹(shù)遷移和樹(shù)恢復(fù)。 圖2給出了內(nèi)部樹(shù)遷移的一個(gè)示例。開(kāi)始時(shí)，移動(dòng)用戶只與數(shù)據(jù)收集樹(shù)中的根節(jié)點(diǎn)A連接。然后，移動(dòng)用戶移動(dòng)到可與其他傳感器直接通信的新的位置。當(dāng)節(jié)點(diǎn)B接收到移動(dòng)用戶的樹(shù)維護(hù)報(bào)文時(shí)，它知道移動(dòng)用戶就在周圍。然后，節(jié)點(diǎn)B成為其子樹(shù)的根，直接與移動(dòng)用戶通信。更新完路由后，節(jié)點(diǎn)B通知其之前的中繼節(jié)點(diǎn)A和移動(dòng)用戶相應(yīng)地更新容量分配策略。

圖2 內(nèi)部樹(shù)遷移示例

當(dāng)根節(jié)點(diǎn)檢測(cè)到與移動(dòng)用戶失去聯(lián)系時(shí)，需要恢復(fù)數(shù)據(jù)收集樹(shù)，樹(shù)的恢復(fù)過(guò)程如圖3所示。一旦根節(jié)點(diǎn)A檢測(cè)到與移動(dòng)用戶失去聯(lián)系，它便向相鄰節(jié)點(diǎn)發(fā)送“FindMobile”樹(shù)恢復(fù)報(bào)文，以便恢復(fù)連接。任何不屬于A的子樹(shù)的節(jié)點(diǎn)，可以幫助把報(bào)文中繼傳輸給移動(dòng)用戶。在該例子中，節(jié)點(diǎn)B為節(jié)點(diǎn)A中繼報(bào)文，于是A與移動(dòng)用戶恢復(fù)連接。與內(nèi)部樹(shù)遷移類似，樹(shù)恢復(fù)后必須相應(yīng)地更新容量。否則，移動(dòng)用戶可能認(rèn)為A已經(jīng)完成數(shù)據(jù)傳輸，但是A實(shí)際上仍在樹(shù)中，且仍有很多數(shù)據(jù)待傳。如果樹(shù)恢復(fù)過(guò)程失效，節(jié)點(diǎn)A可以加入其他移動(dòng)用戶仍有空閑容量的數(shù)據(jù)收集樹(shù)。為了避免出現(xiàn)路由環(huán)路，我們?cè)跇?shù)恢復(fù)報(bào)文中加入與移動(dòng)用戶直接連接的子樹(shù)的根ID。只有具有不同子樹(shù)ID的節(jié)點(diǎn)將對(duì)樹(shù)恢復(fù)請(qǐng)求做出響應(yīng)。

圖3 數(shù)據(jù)收集樹(shù)的恢復(fù)過(guò)程

4 仿真評(píng)估

本文利用OMNet++模擬器來(lái)評(píng)估本文算法EQRoute的性能。傳感器和移動(dòng)設(shè)備在非信標(biāo)模式下基于IEEE 802.15.4進(jìn)行通信。無(wú)線頻段為2.4 GHz，數(shù)據(jù)率為250 kbit/s。在1000 m×1000 m區(qū)域上均勻部署100個(gè)傳感器。無(wú)線傳感器的通信范圍R設(shè)置為100 m，且ΔD=100 m。移動(dòng)用戶的移動(dòng)服從隨機(jī)路點(diǎn)模型，且相互獨(dú)立。在評(píng)估EQRoute時(shí)，設(shè)置pH=0.3，pL=0.7，且只考慮一個(gè)移動(dòng)用戶。傳感器的數(shù)據(jù)生成率為8 B/s。在本文實(shí)驗(yàn)中，設(shè)置移動(dòng)用戶的移動(dòng)速度為2 m/s～22 m/s，標(biāo)準(zhǔn)差為0.5 m/s。為了體現(xiàn)本文算法的優(yōu)越性，將其與文獻(xiàn)[12]提出的λ-Flooding算法在泛在數(shù)據(jù)收集方面的性能進(jìn)行了比較。在λ-Flooding算法中，移動(dòng)用戶構(gòu)建一個(gè)全局?jǐn)?shù)據(jù)收集樹(shù)，更新預(yù)先確定的閾值λ對(duì)樹(shù)進(jìn)行更新，以降低數(shù)據(jù)收集的能耗。

圖4(a)給出了EQRoute和λ-Flooding接收到的報(bào)文總量?？梢钥闯?，二者報(bào)文數(shù)量相當(dāng)。然而，本文EQRoute算法的能耗只有λ-Flooding的一半，如圖4b所示。我們認(rèn)為，λ-Flooding算法為了保持與移動(dòng)用戶的連接，需要延長(zhǎng)路徑，導(dǎo)致能耗提高。當(dāng)速度增加時(shí)，λ-Flooding算法的平均跳數(shù)也會(huì)增加，這進(jìn)一步證明了上述分析，如圖4d所示。

圖4 不同方案的仿真結(jié)果比較

圖4c給出了收集到的數(shù)據(jù)消耗的單位成本(跳數(shù))所對(duì)應(yīng)的信息價(jià)值。EQRoute算法單位通信成本的信息價(jià)值，遠(yuǎn)高于λ-Flooding算法，這是因?yàn)楸疚乃惴ㄔ谕ㄐ胚^(guò)程中為高價(jià)值數(shù)據(jù)賦予更高的優(yōu)先權(quán)。我們還發(fā)現(xiàn)，在EQRoute算法中，移動(dòng)用戶速度增加時(shí)單位成本的信息價(jià)值也會(huì)增加。這是因?yàn)橐苿?dòng)用戶快速移動(dòng)時(shí)構(gòu)建的數(shù)據(jù)收集樹(shù)，規(guī)模更小，跳數(shù)更少。

5 結(jié) 語(yǔ)

本文針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中存在移動(dòng)用戶這一應(yīng)用場(chǎng)景，提出一種基于信息價(jià)值最大化的泛在數(shù)據(jù)收集算法EQRoute。該算法為分布式算法，允許移動(dòng)用戶根據(jù)自己的移動(dòng)速度來(lái)動(dòng)態(tài)構(gòu)建數(shù)據(jù)收集樹(shù)。它還可以實(shí)現(xiàn)數(shù)據(jù)收集樹(shù)規(guī)模的自適應(yīng)控制，以降低能耗。通過(guò)為攜帶重要信息的數(shù)據(jù)分配高優(yōu)先級(jí)，EQRoute提高了獲取數(shù)據(jù)的信息價(jià)值。算法還支持多個(gè)移動(dòng)用戶間不用傳輸任何協(xié)調(diào)報(bào)文，便可就數(shù)據(jù)收集做出本地決策。仿真實(shí)驗(yàn)表明，本文算法和當(dāng)前最新算法相比，信息價(jià)值提高了50%，能耗降低了50%。在下一步工作中，我們將在含有多個(gè)移動(dòng)用戶的傳感器網(wǎng)絡(luò)測(cè)試床上評(píng)估本文算法的性能。我們還打算通過(guò)預(yù)測(cè)移動(dòng)特點(diǎn)來(lái)進(jìn)一步提高分布式算法的性能。

[1] 陳燕, 張尚尚, 梁俊斌, 等. 無(wú)線傳感網(wǎng)中生命最大化的泛在數(shù)據(jù)收集協(xié)議[J]. 計(jì)算機(jī)應(yīng)用研究, 2014, 31(3): 866-871.

[2] 徐建波, 李仁發(fā). 無(wú)線傳感器網(wǎng)絡(luò)中一種新型的混合型數(shù)據(jù)收集協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 45(2): 254-260.

[3] Ji S, Beyah R, Cai Z. Snapshot and continuous data collection in probabilistic wireless sensor networks [J]. IEEE Transactions on Mobile Computing, 2014, 13(3): 626-637.

[4] 胡升澤, 包衛(wèi)東, 王博, 等. 無(wú)線傳感器網(wǎng)絡(luò)基于多元簇首的分簇?cái)?shù)據(jù)收集算法[J]. 電子與信息學(xué)報(bào), 2014, 36(2): 403-408.

[5] Hackmann G, Guo W, Yan G, et al. Cyber-physical codesign of distributed structural health monitoring with wireless sensor networks [J]. IEEE Transactions onParallel and Distributed Systems, 2014, 25(1): 63-72d

[6] Gu Y, Bozdag D, Ekici E, et al. Partitioning based mobile element scheduling in wireless sensor networks[C]// IEEE International Conference on Sensing, Communication, and Networks(SECON). New Orleans, USA:IEEE Press, 2013: 386-395.

[7] Bisnik N, Abouzeid A, Isler V. Stochastic event capture using mobile sensors subject to a quality metric[J]. IEEE Transactions on Robotics, 2014, 23(4): 676-692.

[8] Xu X, Luo J, Zhang Q. Delay tolerant event collection in sensor networks with mobile sink[C]// Proceedings of IEEE INFOCOM. San Diego, CA, USA: IEEE Press, 2010: 1-9.

[9] He L, Yang Z, Pan J, et al. Evaluating service disciplines for mobile elements in wireless ad hoc sensor networks[C]// Proceedings of IEEE INFOCOM. Orlando, FL, USA: IEEE Press, 2012: 576-584.

[10]Kusy B, Lee H J, Wicke M, et al. Predictive QoS routing to mobile sinks in wireless sensor networks[C]// Proceedings of the 8th ACM/IEEE International Confer-

ence on Information Processing in Sensor Networks(IPSN). San Francisco, CA, USA: ACM Press, 2009: 109-120.

[11]Lee H J, Wicke M, Kusy B, et al. Data stashing: energy-efficient information delivery to mobile sinks through trajectory prediction[C]//Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks(IPSN). Stockholm, Sweden: ACM Press, 2010: 291-302.

[12]Li Z, Liu Y, Li M, et al. Exploiting ubiquitous data collection for mobile users in wireless sensor networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(2): 312-326.

[13]Kho J, Rogers A, Jennings N R. Decentralized control of adaptive sampling in wireless sensor networks [J]. ACM Transactions on Sensor Networks (TOSN), 2009, 5(3): 19-30.

關(guān)于《中國(guó)電子科學(xué)研究院學(xué)報(bào)》啟用在線采編系統(tǒng)的通知

尊敬的作者：

您好,為了更好地服務(wù)于廣大作者、審稿專家和讀者,方便查詢論文信息、投稿、詢稿及審稿,提高雜志工作效率,《中國(guó)電子科學(xué)研究院學(xué)報(bào)》編輯部引進(jìn)了期刊在線采編系統(tǒng),目前已經(jīng)正式開(kāi)通，請(qǐng)您登陸如下網(wǎng)址，并注冊(cè)進(jìn)行投稿。在線采編系統(tǒng)啟用后，我們將不再接收電子郵件投稿，造成不便，敬請(qǐng)諒解。

《中國(guó)電子科學(xué)研究院學(xué)報(bào)》在線采編系統(tǒng)網(wǎng)址：http://kjpl.cbpt.cnki.net。

在使用中如果有任何問(wèn)題，請(qǐng)您及時(shí)與編輯部聯(lián)系，聯(lián)系電話：010-68893411

郵箱：dkyxuebao@vip.126.com

《中國(guó)電子科學(xué)研究院學(xué)報(bào)》編輯部

2016年4月20日

Ubiquitous Data Gathering Algorithm Based on Maximization of Information Gain in Wireless Sensor Networks

SONG San-hua

(College of Information Engineering, HuangHuai University, Henan Zhumadian 463000, China)

Ubiquitous data gathering based on mobile devices is a hot research topic at present. However, the existing data gathering schemes work has been focusing on the reliability and energy efficiency on data gathering. The information value carried by the sensing data has not yet been fully considered in data gathering for mobile sensor networks. In addition, the mobile users may not have enough contact time to collect all the data from the surrounding sensors. Hence, it is important to collect data that contain the most valuable information for the users. In this paper, a ubiquitous data gathering algorithm based on maximization of information gain is proposed. Which utilizes the estimated available capacity of mobile devices and the sensor demands to automatically determine the maximum layer for constructing the data collection tree, and then supports data collection for multiple mobile users with uncontrolled mobility in a distributed manner by migrating of data collection tree. In addition, the mobile users can estimate their available capacity for data collection dynamically according to their moving speeds. The simulation results show that the proposed algorithm can improve information value up to 50% and reduce energy consumption to 50% compared with the current latest approach.

Mobile devices; Wireless sensor networks; Ubiquitous data gathering; Information gain

10.3969/j.issn.1673-5692.2017.04.008

2017-05-01

2017-07-07

河南省科技廳發(fā)展計(jì)劃項(xiàng)目(142102110088)

宋三華(1981—)，男，河南人，碩士，講師，主要研究方向?yàn)榫W(wǎng)絡(luò)及Android嵌入式系統(tǒng)應(yīng)用;

E-mail： cjswzyhh@163.com

TP393

A

1673-5692(2017)04-371-07