無線傳感器網(wǎng)絡(luò)延遲約束的MDC分布式軌道規(guī)劃算法*

劉文軍,王 喜,林政寬

(1.蘇州工業(yè)職業(yè)技術(shù)學(xué)院軟件與服務(wù)外包學(xué)院,江蘇 蘇州 215104;2.蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 蘇州 215006)

嵌入式系統(tǒng)和無線通信技術(shù)的進(jìn)步催生了無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)的產(chǎn)生。由于傳感節(jié)點(diǎn)傳輸范圍有限,WSNs通常采用多跳通信,這使得對(duì)大規(guī)模區(qū)域的監(jiān)測(cè)成為可能。近幾年的研究成果表明,在WSNs中引入移動(dòng)元素MEs(Mobile Elements)可以有效解決傳統(tǒng)WSNs面臨的能效等問題,并且能夠有效降低成本、提高系統(tǒng)的可靠性[1-6]。

當(dāng)前數(shù)據(jù)收集模式中采用移動(dòng)數(shù)據(jù)收集器MDC(Mobile Data Collector)訪問網(wǎng)絡(luò)中的所有傳感節(jié)點(diǎn)能夠最大化能量效率,然而由于MDC移動(dòng)速度有限,當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí),該模式面臨顯著的時(shí)延瓶頸。為了解決該問題,基于Rendezvous的移動(dòng)數(shù)據(jù)收集模式成為一種高效的替代方法[7-12]。在該模式中,傳感區(qū)域中的一個(gè)節(jié)點(diǎn)子集首先基于某種策略被選為集結(jié)點(diǎn)RPs(Rendezvous Points)。數(shù)據(jù)傳輸過程中,節(jié)點(diǎn)從其附屬節(jié)點(diǎn)匯聚局部數(shù)據(jù),由其緩存并等待移動(dòng)數(shù)據(jù)收集器到達(dá)時(shí)上載數(shù)據(jù)。值得注意的是從傳感節(jié)點(diǎn)到RP之間的傳輸跳數(shù)應(yīng)當(dāng)加以限制[9,13]。首先,WSNs的固有特征要求高的能量效率。采用多跳中繼數(shù)據(jù)容易因漏斗效應(yīng)導(dǎo)致傳感節(jié)點(diǎn)間能量消耗不平衡,特別是跳數(shù)過多時(shí)愈發(fā)明顯。第二,中繼跳數(shù)過大意味著RP節(jié)點(diǎn)應(yīng)當(dāng)具有強(qiáng)的節(jié)點(diǎn)性能,因?yàn)樵贛DC到達(dá)前這些節(jié)點(diǎn)應(yīng)當(dāng)有足夠的存儲(chǔ)空間來緩存和處理數(shù)據(jù)。這對(duì)能量和功能受限的傳感節(jié)點(diǎn)來說是不切實(shí)際的。最后,諸如實(shí)時(shí)監(jiān)測(cè)之類的應(yīng)用往往對(duì)時(shí)延要求苛刻,而中繼跳數(shù)過大或無法預(yù)測(cè)均不能很好地滿足該需要。

1 問題定義

1.1 網(wǎng)絡(luò)模型

在基于Rendezvous 的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集應(yīng)用中,源節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)需要被持續(xù)不斷地發(fā)送到RP進(jìn)行緩存,等待MDC近距離進(jìn)行收集,因此需要確立數(shù)據(jù)匯聚的路由和MDC的移動(dòng)軌跡。

無線傳感器網(wǎng)絡(luò)通過無向圖G(V,E)來模擬,其中頂點(diǎn)集V表示所有傳感節(jié)點(diǎn),邊集E表示連接相鄰節(jié)點(diǎn)的通信鏈路。V中的兩個(gè)頂點(diǎn)u和v是相鄰的當(dāng)且僅當(dāng)它們?cè)诒舜说耐ㄐ欧秶鷥?nèi),稱u是v的鄰居,反之亦然。圖G中的一條路徑P=p(v1,vl)=是l個(gè)不相同頂點(diǎn)的序列,使得任意兩個(gè)連續(xù)的頂點(diǎn)是相鄰的,其長(zhǎng)度 |P|=l-1(l>1)。u,v之間的最短路徑的長(zhǎng)度叫做u,v間的距離,記作d(u,v)。網(wǎng)絡(luò)G的直徑是指任意兩個(gè)節(jié)點(diǎn)間距離的最大值,記為dG。頂點(diǎn)v的鄰居是所有G中與v相鄰的所有頂點(diǎn)集,記為N(v)。對(duì)任意的v∈V和一個(gè)非負(fù)整數(shù)k,v的k跳鄰居定義為k-NG(v)(簡(jiǎn)記為k-N(v)),按照慣例,0-NG(v)={v}。

基于潛在通信拓?fù)銰,通過一個(gè)有向匯聚樹的集合T={Ti}來表示數(shù)據(jù)收集應(yīng)用中實(shí)際的數(shù)據(jù)傳輸路由。對(duì)任意的一棵路由樹Ti(0

為了研究問題的方便,在參考現(xiàn)有文獻(xiàn)的基礎(chǔ)上,我們對(duì)傳感節(jié)點(diǎn)和潛在網(wǎng)絡(luò)模型作出以下假定:

①假定N個(gè)同質(zhì)的傳感節(jié)點(diǎn)隨機(jī)分布于規(guī)則的傳感區(qū)域,不考慮障礙物影響,在確定的通信半徑下所有通信鏈路都是對(duì)稱的。

②MDC位于網(wǎng)絡(luò)中的某處以可控制性移動(dòng)模式移動(dòng)在網(wǎng)絡(luò)中漫游。MDC資源和功能均不受限制。

③傳感節(jié)點(diǎn)首先通過有限跳通信將數(shù)據(jù)傳遞到選出的支配節(jié)點(diǎn)DNs(Dominating Nodes)進(jìn)行緩存,假定普通傳感節(jié)點(diǎn)的存儲(chǔ)容量足夠大,從而在被確定為DN后能夠在MDC到達(dá)前緩存附屬節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)。僅當(dāng)MDC停留在任一DN通信范圍內(nèi)請(qǐng)求數(shù)據(jù)上載,傳感節(jié)點(diǎn)啟動(dòng)數(shù)據(jù)傳輸。

④假定MDC裝備有全球定位系統(tǒng)GPS(Global Positioning System)單元或其他位置服務(wù)模塊,從而能夠確定自身的物理位置。出于一般性考慮,普通傳感節(jié)點(diǎn)不具備以上功能。

⑤沿著多跳路徑傳輸一個(gè)數(shù)據(jù)包的總能量消耗與發(fā)送者和接受者之間的歐氏距離成比例。

1.2 問題定義

本文MDC最小延遲軌道規(guī)劃問題的解決主要基于k跳支配集的構(gòu)建,以支配節(jié)點(diǎn)DNs充當(dāng)RP,因而首先正式給出k跳支配集的概念。

定義1圖G(V,E)的一個(gè)k跳支配集是一個(gè)子集D?V,滿足對(duì)于VD中的任意一個(gè)頂點(diǎn)v,存在某個(gè)頂點(diǎn)u∈D,使得從v到該頂點(diǎn)的距離至多為k。

基于Rendezvous模式的移動(dòng)數(shù)據(jù)收集問題中,MDC從初始位置啟動(dòng)每次數(shù)據(jù)收集過程,MDC在遍歷所有RN后最終返回到初始位置。支配節(jié)點(diǎn)確定了MDC行進(jìn)軌道的錨點(diǎn),在MDC速度保持不變的情況下,軌道長(zhǎng)度決定了數(shù)據(jù)收集的時(shí)延。問題的需求是在k跳支配約束下MDC移動(dòng)軌跡長(zhǎng)度盡可能短,以達(dá)到縮短數(shù)據(jù)收集時(shí)延的目的。該問題中MDC 的路徑規(guī)劃和以支配節(jié)點(diǎn)為根的匯聚樹中的路由需要聯(lián)合進(jìn)行考慮以尋找到整體最優(yōu)解。我們稱該問題為基于k跳支配集的MDC最小時(shí)延規(guī)劃問題MLP-kDS(Minimum Latency Planning of MDC based onk-hop Dominating Sets),并將其定義如下:

定義2給定一個(gè)傳感節(jié)點(diǎn)集合S={s1,s2,…,sN} 和中繼跳約束k,在網(wǎng)絡(luò)G中尋找一個(gè)連接π和D中所有節(jié)點(diǎn)的MDC的軌道U,要求滿足如下條件:

D2-1 一個(gè)最小規(guī)模的k-DS集合D,其分布盡可能靠近MDC的初始位置π;

D2-2 ∑(u,v)∈ U|uv|是最小的,其中(u,v)是軌道U上的路線,|uv|表示其歐式距離;

D2-3 一個(gè)以D中節(jié)點(diǎn)為根高度至多為k的匯聚樹集合T={Ti(Vi,Ei)},使得UiVi=S且∑i∑(u,v)∈ Ei|uv|最小。

從定義可見,以獲得盡可能短的MDC軌道為目標(biāo),DN的個(gè)數(shù)與分布、訪問次序、以及每棵特定的以DN為根滿足中繼跳限約束的匯聚樹形態(tài)分別通過條件 D2-1,D2-2和D2-3 給出,求解時(shí)應(yīng)聯(lián)合加以考慮。對(duì)V中任意的r和v,如果存在一條從v到r的路徑,則稱頂點(diǎn)v被頂點(diǎn)r覆蓋。如果該路徑的長(zhǎng)度為k,則稱頂點(diǎn)v是由r所k跳覆蓋的。實(shí)際上,網(wǎng)絡(luò)中的一個(gè)傳感節(jié)點(diǎn)集合被r所覆蓋意味著產(chǎn)生了一棵從這些節(jié)點(diǎn)收集信息并匯聚到根節(jié)點(diǎn)r的數(shù)據(jù)匯聚樹。k跳覆蓋保證了來自任意數(shù)據(jù)源的數(shù)據(jù)包在不超過k個(gè)中繼跳被發(fā)送到r。參數(shù)k的設(shè)置取決于用戶的需求,反映了能量效率和數(shù)據(jù)收集時(shí)延之間的平衡。

定理1MLP-kDS問題是NP難的。

證明MLP-kDS 問題包含3個(gè)相關(guān)條件。Amis等證明單位圓盤圖最小k跳支配集是NP完全的[14]。以下證明即便不考慮k-DSs的規(guī)模,最短MDC軌跡問題仍然是NP難的,這可以通過從一個(gè)給定的歐氏旅行售貨商問題TSP(Traveling Salesman Problem)的多項(xiàng)式時(shí)間歸約到問題的一個(gè)特例來證明。給定一個(gè)網(wǎng)絡(luò)G=(V,E)作為TSP問題的實(shí)例。條件 D2-2 決議版的一個(gè)特例是判定是否存在一個(gè)DN的集合包含網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。這可以通過調(diào)整節(jié)點(diǎn)的通信范圍Rt完成。當(dāng)Rt足夠小,節(jié)點(diǎn)相互間均是不可達(dá)的。此時(shí),中繼跳數(shù)k恰好等于0,MDC必須訪問所有的傳感節(jié)點(diǎn)來收集數(shù)據(jù)。該情況下意味著所有節(jié)點(diǎn)都是DN。這恰好是一般的旅行售貨商問題。所以MLP-kDS是NP難的。

2 k-DDSR算法

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

由于MLP-kDS問題是NP 難的,本節(jié)給出一個(gè)分布式的k跳DN確定算法k-DDSR(Distributedk-hop Dominating Sets and Routing)來解決定義的問題。算法的主要思想是首先構(gòu)建網(wǎng)絡(luò)G的k-跳支配集以及每個(gè)成員節(jié)點(diǎn)所附屬的支配節(jié)點(diǎn),后者構(gòu)成通信時(shí)的路由樹。所構(gòu)建的支配節(jié)點(diǎn)應(yīng)滿足如下條件:支配節(jié)點(diǎn)的規(guī)模|D|盡可能小、負(fù)載盡可能均衡、位置盡可能靠近MDC初始位置,從而使得最終生成的MDC的軌跡長(zhǎng)度盡可能短。

定義3網(wǎng)絡(luò)中給定以r為根的路由樹Ti,若從當(dāng)前節(jié)點(diǎn)si到祖先節(jié)點(diǎn)sj的距離為d,即dist(si,sj)=d,則稱節(jié)點(diǎn)sj是Ti中si的d父節(jié)點(diǎn),記為d-PN。

給定通信范圍Rt下的網(wǎng)絡(luò)G(V,E)、MDC初始位置π和跳限參數(shù)k,由任意傳感節(jié)點(diǎn)si執(zhí)行的分布式的k跳支配集D和路由樹集T構(gòu)建算法過程如圖1所示。

圖1 k-DDSR算法流程圖

Step 1 節(jié)點(diǎn)標(biāo)識(shí)符分配 初始時(shí)每個(gè)節(jié)點(diǎn)依據(jù)信號(hào)強(qiáng)度按照距離MDC起始位置π的距離分配一個(gè)ID,距離π越遠(yuǎn)得到的ID越大,反之,ID越小。

Step 2 節(jié)點(diǎn)狀態(tài)及路由確定 如果當(dāng)前節(jié)點(diǎn)si的距離標(biāo)識(shí)符大于所有鄰居的標(biāo)識(shí)符,則節(jié)點(diǎn)si變?yōu)槌蓡T節(jié)點(diǎn)狀態(tài),記為“MN”,si記錄ID號(hào)最小的鄰居為其路由樹的d-PN,d≤k,并從原網(wǎng)絡(luò)中剪除與之關(guān)聯(lián)的其他通信邊/鏈路。

特別地,如果si與其狀態(tài)未確定鄰居構(gòu)成局部全連接網(wǎng)絡(luò)(任意兩個(gè)節(jié)點(diǎn)都存在通信邊),且si∪N(si)比其鄰居的ID更大,則除了ID號(hào)最小的鄰居外均變?yōu)椤癕N”,si記錄ID號(hào)最小的鄰居為其路由樹的1-PN。

Step 3 通過k-PN迭代確定DN 重復(fù)Step 2至多k次。每次迭代過程中,如果si自身為i-PN,則si選擇的新父節(jié)點(diǎn)記為(i+1)-PN,si本身變?yōu)槌蓡T節(jié)點(diǎn)。不足k次,則該節(jié)點(diǎn)確定自身狀態(tài)為DN,終止循環(huán)。

對(duì)Step 3確定的網(wǎng)絡(luò)中的k-PN,令其狀態(tài)為DN。

Step 4 通過消息轉(zhuǎn)發(fā)確定DN所屬成員及路由 所有DN向k跳范圍內(nèi)尚未確定父節(jié)點(diǎn)的鄰居發(fā)送(轉(zhuǎn)發(fā))DN聲明消息DEC_MSG(ID,r,i),最先收到該消息的i-PN或狀態(tài)未確定的節(jié)點(diǎn)變?yōu)镈N的成員節(jié)點(diǎn),記錄自身的i-PN,并從網(wǎng)絡(luò)中剪除到ID比自身大的通信邊。DEC_MSG消息至多傳輸k跳后結(jié)束,此時(shí)形成第1批k跳支配節(jié)點(diǎn)及受其支配的成員節(jié)點(diǎn)。

Step 5 算法迭代確定所有節(jié)點(diǎn)狀態(tài)及路由 對(duì)網(wǎng)絡(luò)中所有狀態(tài)未確定的節(jié)點(diǎn),繼續(xù)執(zhí)行Step2～Step4,直至每個(gè)節(jié)點(diǎn)要么是“MN”,要么是“DN”。特別地,對(duì)不連通網(wǎng)絡(luò)會(huì)同時(shí)運(yùn)行上述算法。

以下通過圖2舉例說明當(dāng)k=2時(shí)算法的執(zhí)行情況:圖2(a)給出了29個(gè)節(jié)點(diǎn)和一個(gè)MDC及其初始位置π時(shí)的網(wǎng)絡(luò)配置情況。其中,節(jié)點(diǎn)旁邊的數(shù)字為依據(jù)位置π生成的距離標(biāo)識(shí)符。假定節(jié)點(diǎn)的狀態(tài)用不同的顏色匹配,其中“MN”(灰色節(jié)點(diǎn)),“DN”(黑色節(jié)點(diǎn)),“UN”(白色節(jié)點(diǎn))。初始時(shí)所有節(jié)點(diǎn)狀態(tài)均為“UN”。圖2(b)給出算法執(zhí)行第1輪中確定首批成員節(jié)點(diǎn)的情形。圖2(c)給出算法執(zhí)行第1輪中確定第2批成員節(jié)點(diǎn)的情形,其中節(jié)點(diǎn)6、7、12、14組成2-PN,充當(dāng)DN并向網(wǎng)絡(luò)中的2跳鄰居發(fā)送DN聲明消息來招募成員。接收到消息的節(jié)點(diǎn),包括狀態(tài)未確定的節(jié)點(diǎn)及1-PN,選擇加入距離最近的DN,自身變?yōu)槌蓡T節(jié)點(diǎn)。最后,圖2(d)給出最終的DN、MN和按照貪心算法生成的MDC軌跡。從圖2可以看出,對(duì)于一個(gè)由27個(gè)節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò),算法僅執(zhí)行一輪即可構(gòu)建出中繼跳數(shù)為2的支配節(jié)點(diǎn)和相應(yīng)的路由樹,表明了所提出的分布式算法的高效性。

圖2 k-DDSR算法執(zhí)行示例

2.2 MDC軌跡長(zhǎng)度

給定k-DS的集合D和初始位置π,以下步驟給出求解MDC軌跡U的過程。

Step 1 基于確定的k-DS集合D,通過Prim算法構(gòu)建以π為根的MSTTR。

Step 2 對(duì)TR應(yīng)用Christofides 1.5-近似算法[15]生成解U。

采用Prim算法求解TR時(shí)間復(fù)雜度為O(|D|2)?；赥R采用Christofides 1.5-近似算法產(chǎn)生U的時(shí)間復(fù)雜度為O(|D|3+N),此處|D|和N分別為k-DS的規(guī)模和網(wǎng)絡(luò)規(guī)模。

3 算法效率分析

本節(jié)分析k-DDSR算法的執(zhí)行效率,首先給出正確性證明,然后給出k跳支配集的規(guī)模,最后呈現(xiàn)時(shí)間和消息復(fù)雜度分析。

定理2k-DDSR算法執(zhí)行結(jié)束后,任意節(jié)點(diǎn)要么是支配節(jié)點(diǎn),要么是成員節(jié)點(diǎn)且該節(jié)點(diǎn)到支配節(jié)點(diǎn)的路由跳數(shù)不超過k。

證明算法的正確正確執(zhí)行由算法中的兩個(gè)關(guān)鍵步驟保證:一個(gè)是成員節(jié)點(diǎn)的確定(Step 2);另一個(gè)是k-PN的確定(Step3),分為正常結(jié)束和提前終止操作步驟兩種情況。其中“k-PN”保證DN對(duì)MN的k跳覆蓋。被確定為k-PN的支配節(jié)點(diǎn)總是從局部最遠(yuǎn)節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路由跳數(shù)為k,然后k-PN向其k跳鄰居發(fā)送聲明消息;“提前終止”保證當(dāng)網(wǎng)絡(luò)規(guī)模相對(duì)較小時(shí)仍能夠選出DN,對(duì)成員節(jié)點(diǎn)進(jìn)行支配,從而保證算法正常結(jié)束。

定理3給定網(wǎng)絡(luò)規(guī)模為N直徑為dG的連通無線傳感器網(wǎng)絡(luò)G,k-DS的規(guī)模滿足 |D|≤?N/(k+1)」,1≤k≤dG。

證明:算法一次迭代后確定i-PN,分為兩種情況:

情況1i

情況2i=k任意標(biāo)記為k-PN的節(jié)點(diǎn)y向其k跳鄰居k-NG(y)發(fā)送DN聲明消息。最壞情況下,無新的DN生成,因此每個(gè)支配節(jié)點(diǎn)僅包含k個(gè)成員節(jié)點(diǎn),如圖3(b)所示。

綜上,兩種情況下k-DS的規(guī)模滿足 |D|≤?N/(k+1)」。

圖3 k-DDSR算法證明

定理4給定規(guī)模為N的無線傳感器網(wǎng)絡(luò)G,采用k-DDSR算法確定k-DS和數(shù)據(jù)匯聚樹集T所需的最壞時(shí)間復(fù)雜度為O(dG/k),其中dG為網(wǎng)絡(luò)直徑。

證明算法以迭代方式運(yùn)行,迭代過程中隨著節(jié)點(diǎn)狀態(tài)的確定節(jié)點(diǎn)不斷從原網(wǎng)絡(luò)中剪除,從而網(wǎng)絡(luò)的規(guī)模(直徑)逐漸變小,直至為1。

節(jié)點(diǎn)僅知道其直接鄰居信息,在每次迭代中,節(jié)點(diǎn)首先確定其臨時(shí)父節(jié)點(diǎn)(i-PN),自身狀態(tài)變?yōu)椤癕N”,當(dāng)循環(huán)執(zhí)行完畢,k-PN發(fā)送DN聲明消息,成員節(jié)點(diǎn)加入相應(yīng)的支配節(jié)點(diǎn),該過程需要O(k)時(shí)間。因而,在一次循環(huán)中所需要的時(shí)間復(fù)雜度為O(2k)。

最壞情況下,當(dāng)MDC位于網(wǎng)絡(luò)的邊緣,此時(shí)算法迭代從網(wǎng)絡(luò)的最遠(yuǎn)端開始。由于每次迭代花費(fèi)的時(shí)間為O(2k),共需要迭代次數(shù)為dG/2k,因而總的時(shí)間花費(fèi)為O(dG/k)。

定理5給定中繼跳限為k的無線傳感器網(wǎng)絡(luò)G,采用k-DDSR算法解決MLP-kDS問題時(shí)每個(gè)節(jié)點(diǎn)的消息交換復(fù)雜度為O(1)。

證明網(wǎng)絡(luò)中確定的任意一個(gè)支配節(jié)點(diǎn)首先向其除孩子節(jié)點(diǎn)外的直接鄰居發(fā)送DN聲明消息,消息在網(wǎng)絡(luò)中至多傳播k跳。網(wǎng)絡(luò)中任一節(jié)點(diǎn)收到來自不同節(jié)點(diǎn)發(fā)送的DEC_MSG消息,僅記錄首先收到的節(jié)點(diǎn)為父節(jié)點(diǎn),并轉(zhuǎn)發(fā)給其余鄰居,后續(xù)收到的聲明消息被丟棄。

算法依次方法迭代,網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)最多只收到一次聲明消息和轉(zhuǎn)發(fā)一次聲明消息,因此消息交換復(fù)雜度為O(1)。

4 系統(tǒng)仿真

4.1 仿真設(shè)定

前文中給出了解決MLP-kDS問題的分布式算法其性能分析。本節(jié)通過仿真實(shí)驗(yàn)對(duì)所提出的算法進(jìn)行性能評(píng)估,并呈現(xiàn)仿真結(jié)論。仿真采用Java語言實(shí)現(xiàn),選擇一臺(tái)2核8G內(nèi)存臺(tái)式機(jī)上進(jìn)行,仿真參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

網(wǎng)絡(luò)時(shí)延主要包括節(jié)點(diǎn)到DN的路由時(shí)間和MDC以一定速度遍歷所有DN的時(shí)間兩個(gè)方面。由于數(shù)據(jù)路由時(shí)間可以忽略,因而主要考察后者引起的時(shí)延。仿真關(guān)注的性能量度主要包括:

①DN的數(shù)目(NDN)。在中繼跳數(shù)確定下,DN的數(shù)目直接影響MDC的軌跡長(zhǎng)度。節(jié)點(diǎn)數(shù)目越多,MDC遍歷所有DN節(jié)點(diǎn)所生成的移動(dòng)軌跡越長(zhǎng)。

②MDC軌跡長(zhǎng)度(LMDC)。在MDC移動(dòng)速度確定下,遍歷所有MDC花費(fèi)的時(shí)間可以映射為軌跡長(zhǎng)度。

仿真中通過變換節(jié)點(diǎn)通信范圍Rt,中繼跳限k,網(wǎng)絡(luò)規(guī)模N等參數(shù)來評(píng)估算法的性能,將其與當(dāng)前類似的移動(dòng)數(shù)據(jù)收集算法PB-PSA[9],AT-DRDA[12]和TRACK[16]進(jìn)行性能比較。TRACK 為基于連通支配集的匯點(diǎn)移動(dòng)數(shù)據(jù)收集模型。PB-PSA和AT-DRDA算法均用于解決中繼跳數(shù)約束的MDC數(shù)據(jù)收集問題,其中 PB-PSA 以分布式方式獲得理想的集結(jié)點(diǎn),該算法采用了兩個(gè)參數(shù)用來指導(dǎo)RP的選擇過程,一個(gè)參數(shù)是當(dāng)前節(jié)點(diǎn)的d跳鄰居個(gè)數(shù),另一個(gè)參數(shù)為當(dāng)前節(jié)點(diǎn)到數(shù)據(jù)匯點(diǎn)的最小跳數(shù)。分布式的AT-DRDA算法基于最短路徑樹以迭代方式確定RP。

4.2 仿真結(jié)論

仿真中,我們考慮一個(gè)具有N個(gè)節(jié)點(diǎn)隨機(jī)分布于200 m×200 m正方形區(qū)域的傳感器網(wǎng)絡(luò),MDC的位置處于傳感區(qū)域的中心。在MDC到達(dá)各節(jié)點(diǎn)前每個(gè)數(shù)據(jù)包在中繼跳限k的約束下局部地匯聚到DN上進(jìn)行緩存。仿真過程中我們采用最近鄰居NN(Nearest Neighbor)算法[17]來產(chǎn)生MDC的移動(dòng)軌跡?？紤]網(wǎng)絡(luò)拓?fù)涞碾S機(jī)性,盡可能最小化性能誤差,圖中的每個(gè)性能點(diǎn)是對(duì)100次試驗(yàn)取平均值獲得的結(jié)果。

以下給出不同網(wǎng)絡(luò)規(guī)模下算法k-DDSR與TRACK、PB-PSA 和 AT-DRDA的性能對(duì)比。參數(shù)Rt和k分布設(shè)為30 m和2。評(píng)估不同網(wǎng)絡(luò)規(guī)模下支配節(jié)點(diǎn)的數(shù)目(NDN)和MDC軌跡(LMDC)的長(zhǎng)度。圖4和圖5繪制了不同算法隨著N從50逐漸增到400過程中的性能對(duì)比。對(duì)于NDN和N的關(guān)系,算法k-DDSR總體上優(yōu)于其他兩種分布式算法。

圖4 網(wǎng)絡(luò)規(guī)模N與延遲DN規(guī)模的關(guān)系

圖5 數(shù)據(jù)傳播延遲與MDC移動(dòng)速度的關(guān)系

為了保證MDC的移動(dòng)軌跡盡可能短,算法中k-DS的選擇主要考慮兩個(gè)因素:一是其位置分布盡可能逼近MDC的初始位置π,另外保證其規(guī)模盡可能小。在確定的中繼跳限k,如果MDC的平均移動(dòng)速度不變,則軌跡長(zhǎng)度越小,意味著數(shù)據(jù)收集的間延遲越短。因此,圖4中較小的NDN規(guī)模對(duì)應(yīng)圖5中更短的MDC移動(dòng)軌跡。當(dāng)節(jié)點(diǎn)規(guī)模為400時(shí),分別比AT-DRDA、PB-PSA和TRACK算法生成軌跡長(zhǎng)度降低10.2%、14.3%、20.1%。

5 結(jié)論

本文研究了基于Rendezvous模式的移動(dòng)數(shù)據(jù)收集軌道規(guī)劃問題MLP-kDS及其形式化定義?；趉跳支配集給出了k-DS節(jié)點(diǎn)分布式構(gòu)建算法k-DDSR。算法的主要思想是針對(duì)無線傳感器網(wǎng)絡(luò)特征以分布式方式從網(wǎng)絡(luò)邊緣向中心迭代確定集結(jié)點(diǎn),并且聯(lián)合考慮MDC的軌跡和數(shù)據(jù)匯聚樹的路由。所提出算法的效果通過理論分析和仿真實(shí)驗(yàn)進(jìn)行評(píng)估,理論上證明了算法的正確性,并給出了k-DS 的規(guī)模界以及時(shí)間和消息交換復(fù)雜度。仿真實(shí)驗(yàn)表明,相比同類算法AT-DRDA,MDC的軌跡長(zhǎng)度縮短了10.2%。