帶有移動(dòng)Sink的傳感器網(wǎng)絡(luò)回路避免跟蹤協(xié)議

徐慧芬，鄔春學(xué)，楊桂松

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

?

帶有移動(dòng)Sink的傳感器網(wǎng)絡(luò)回路避免跟蹤協(xié)議

徐慧芬，鄔春學(xué)，楊桂松

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

無線傳感器網(wǎng)絡(luò)通常被應(yīng)用于收集大規(guī)模網(wǎng)絡(luò)中的傳感數(shù)據(jù)，這些收集工作由Sink完成。為了降低網(wǎng)絡(luò)內(nèi)能量空洞產(chǎn)生的概率，延長(zhǎng)網(wǎng)絡(luò)壽命，目前多采用移動(dòng)Sink收集數(shù)據(jù)。文中提出了一種帶有移動(dòng)Sink的數(shù)據(jù)收集協(xié)議。該協(xié)議中，Sink節(jié)點(diǎn)能根據(jù)相鄰足跡節(jié)點(diǎn)間坐標(biāo)夾角的變化,有效回避掉那些回路上的足跡節(jié)點(diǎn)，而只保留非回路上的足跡節(jié)點(diǎn)。仿真實(shí)驗(yàn)結(jié)果表明，LAT協(xié)議可顯著提升數(shù)據(jù)查詢效率，并有效延長(zhǎng)了網(wǎng)絡(luò)壽命。

移動(dòng)Sink；數(shù)據(jù)查詢； LAT協(xié)議；回路避免

無線傳感器網(wǎng)絡(luò)由大量?jī)r(jià)格低廉，處理能力較弱的傳感器節(jié)點(diǎn)組成，其應(yīng)用范圍廣泛，從精密的軍事領(lǐng)域到傳感信息繁多的農(nóng)業(yè)領(lǐng)域。這些網(wǎng)絡(luò)的規(guī)模通常較大，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量較多，所需采集的數(shù)據(jù)類型較多，數(shù)據(jù)量大，且呈現(xiàn)出分布式特征。

在無線傳感網(wǎng)中存在一個(gè)匯聚節(jié)點(diǎn)(Sink)用來收集傳感器節(jié)點(diǎn)感知到的數(shù)據(jù)[1-6]。當(dāng)Sink是靜態(tài)時(shí)，傳感器節(jié)點(diǎn)會(huì)根據(jù)指定的位置將感知數(shù)據(jù)路由給Sink，但這樣會(huì)使Sink附近的傳感器節(jié)點(diǎn)能量快速消耗，造成能量黑洞，從而縮短網(wǎng)絡(luò)壽命。因而現(xiàn)在的研究中，Sink大多是移動(dòng)的。但由于Sink的移動(dòng)性，網(wǎng)絡(luò)中的普通節(jié)點(diǎn)不能獲得移動(dòng)Sink的位置信息，無法進(jìn)行數(shù)據(jù)傳輸[7-8]。

有研究者提出了根據(jù)Sink的移動(dòng)軌跡預(yù)測(cè)進(jìn)行數(shù)據(jù)傳輸?shù)穆酚蓞f(xié)議[9-11]，但該種方法對(duì)于Sink軌跡的預(yù)測(cè)并不適用于實(shí)際情況且有移動(dòng)的局限性[12]。因而，本文提出了一種基于移動(dòng)Sink的數(shù)據(jù)查詢解決方法，當(dāng)Sink需要查詢其所在區(qū)域的傳感信息時(shí)，首先就近指定一個(gè)區(qū)域代理節(jié)點(diǎn)，然后向該代理節(jié)點(diǎn)發(fā)送數(shù)據(jù)查詢請(qǐng)求。Sink完成數(shù)據(jù)查詢請(qǐng)求后繼續(xù)移動(dòng)，并在之后的移動(dòng)過程中每隔一段時(shí)間記一次足跡節(jié)點(diǎn)。隨著Sink節(jié)點(diǎn)的移動(dòng)，雖其所標(biāo)記的足跡節(jié)點(diǎn)的坐標(biāo)連線完整的記錄了Sink的移動(dòng)軌跡，但由于該移動(dòng)軌跡的隨機(jī)性而不可避免的會(huì)出現(xiàn)路徑回路。通過采用LAT算法，可有效解決路徑回路的問題。

1 網(wǎng)絡(luò)模型設(shè)計(jì)

假設(shè)網(wǎng)絡(luò)中有大量隨機(jī)部署的傳感器節(jié)點(diǎn)以及一個(gè)或多個(gè)移動(dòng)Sink節(jié)點(diǎn)。初始化網(wǎng)絡(luò)時(shí)，每個(gè)傳感器節(jié)點(diǎn)均分配了位置坐標(biāo)。同時(shí)，網(wǎng)絡(luò)中的節(jié)點(diǎn)被劃分為以下類型：移動(dòng)Sink節(jié)點(diǎn)，區(qū)域代理節(jié)點(diǎn)，足跡節(jié)點(diǎn)，LAT 節(jié)點(diǎn)以及普通節(jié)點(diǎn)。其中，區(qū)域代理節(jié)點(diǎn)和足跡節(jié)點(diǎn)均是由Sink節(jié)點(diǎn)指定的。

1.1 移動(dòng) Sink

網(wǎng)絡(luò)中的移動(dòng)Sink節(jié)點(diǎn)具有強(qiáng)大的計(jì)算能力和存儲(chǔ)容量，Sink通過無線的方式和網(wǎng)絡(luò)中的其他節(jié)點(diǎn)交換信息。每個(gè)Sink配備有GPS模塊，因而可隨時(shí)獲得自身的位置信息。移動(dòng)Sink節(jié)點(diǎn)可收集網(wǎng)絡(luò)中任何區(qū)域的傳感信息，當(dāng)其移動(dòng)至感興趣區(qū)域時(shí)，首先會(huì)廣播代理請(qǐng)求以指定一個(gè)代理節(jié)點(diǎn)。

收到廣播的傳感器節(jié)點(diǎn)若不是其他移動(dòng)Sink的代理節(jié)點(diǎn)，則返回一個(gè)代理確認(rèn)消息。Sink從收到的所有代理確認(rèn)消息中選取距離自身當(dāng)前位置最近的節(jié)點(diǎn)作為該區(qū)域的區(qū)域代理節(jié)點(diǎn)，然后向這一節(jié)點(diǎn)發(fā)送數(shù)據(jù)查詢請(qǐng)求包，包括所要收集數(shù)據(jù)的范圍，收集周期以及收集的數(shù)據(jù)類型。

Sink發(fā)送完數(shù)據(jù)查詢請(qǐng)求后即離開，其移動(dòng)路線具有隨機(jī)性，并每隔一段時(shí)間記錄一次足跡。代理節(jié)點(diǎn)只負(fù)責(zé)收集數(shù)據(jù)，并不追蹤Sink的位置，因而數(shù)據(jù)的收集請(qǐng)求是由Sink主動(dòng)發(fā)起的。

1.2 LAT 節(jié)點(diǎn)

定義1 LAT 節(jié)點(diǎn)是Sink通過LAT協(xié)議判斷后不在路徑回路上的足跡節(jié)點(diǎn)。

LAT 節(jié)點(diǎn)是足跡節(jié)點(diǎn)的子集，規(guī)定Sink最先記錄的兩個(gè)足跡節(jié)點(diǎn)直接標(biāo)記為L(zhǎng)AT節(jié)點(diǎn)。從第3個(gè)足跡節(jié)點(diǎn)開始，Sink每次記錄過足跡節(jié)點(diǎn)后，就會(huì)根據(jù)LAT協(xié)議判斷上一個(gè)足跡節(jié)點(diǎn)是否在回路上，若不在回路上，則認(rèn)為該節(jié)點(diǎn)為L(zhǎng)AT 節(jié)點(diǎn)；若該節(jié)點(diǎn)經(jīng)判斷在回路上，則認(rèn)為其不是LAT節(jié)點(diǎn)，并繼續(xù)判斷上一個(gè)已認(rèn)證過的LAT 節(jié)點(diǎn)是否在回路上，若該LAT節(jié)點(diǎn)也在回路上，則認(rèn)為其不再是LAT節(jié)點(diǎn)，由此遞歸判斷上一個(gè)LAT節(jié)點(diǎn)直到某個(gè)LAT節(jié)點(diǎn)不在回路上或只剩下區(qū)域節(jié)點(diǎn)仍為L(zhǎng)AT節(jié)點(diǎn)。

2 協(xié)議設(shè)計(jì)

2.1 LAT節(jié)點(diǎn)的判斷

為了能清楚描述LAT協(xié)議的工作機(jī)制，在此定義LAT角，并通過比較LAT角來判斷一個(gè)節(jié)點(diǎn)是否處于回路上。

定義2 LAT 角是所判斷節(jié)點(diǎn)與區(qū)域代理節(jié)點(diǎn)所在連線和所判斷節(jié)點(diǎn)與Sink當(dāng)前位置所在連線形成的≤180°的夾角，圖1中∠1。

如圖2所示，D節(jié)點(diǎn)是Sink的當(dāng)前位置，C是當(dāng)前的帶判定節(jié)點(diǎn)也是上一個(gè)記錄的足跡節(jié)點(diǎn)，節(jié)點(diǎn)B是上一個(gè)已判定為L(zhǎng)AT節(jié)點(diǎn)的節(jié)點(diǎn)，其中，∠1是判定節(jié)點(diǎn)B時(shí)的LAT角，∠2是節(jié)點(diǎn)C的LAT角。通過比較∠1和∠2的大小可判斷節(jié)點(diǎn)C是否在回路上。顯然，若∠1<∠2，則說明Sink的移動(dòng)并未產(chǎn)生明顯的回路。此時(shí)，節(jié)點(diǎn)C成為L(zhǎng)AT節(jié)點(diǎn)；若∠1>∠2，則說明Sink產(chǎn)生了明顯的回路，則節(jié)點(diǎn)C不能成為L(zhǎng)AT節(jié)點(diǎn)，且要繼續(xù)判斷節(jié)點(diǎn)B是否依然是LAT節(jié)點(diǎn)。

圖1 LAT 角示意圖

圖2 移動(dòng)路線為非回路時(shí)LAT角的比較

圖3 移動(dòng)路線為回路時(shí)LAT 角的比較

2.2 Sink發(fā)送數(shù)據(jù)收集請(qǐng)求

當(dāng)Sink需要收集數(shù)據(jù)時(shí)，停止移動(dòng)，發(fā)出數(shù)據(jù)收集請(qǐng)求，并將此時(shí)所有的LAT節(jié)點(diǎn)添加到數(shù)據(jù)包中作為數(shù)據(jù)包的傳輸路徑。由于在選取LAT節(jié)點(diǎn)時(shí)篩選掉了一部分足跡節(jié)點(diǎn)，因而兩個(gè)相鄰的LAT節(jié)點(diǎn)間距可能超過節(jié)點(diǎn)的通信范圍。在此，采用定向泛洪的方法可解決這一問題。

定向泛洪對(duì)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的方向進(jìn)行限制，不允許數(shù)據(jù)自由地向四面八方擴(kuò)散[11]。節(jié)點(diǎn)收到定向泛洪數(shù)據(jù)包時(shí)，通過判斷自身是否在泛洪限制的角度范圍來決定是否轉(zhuǎn)發(fā)該數(shù)據(jù)包，這樣不但可快速找到目標(biāo)節(jié)點(diǎn)，還可大量減少網(wǎng)絡(luò)中重復(fù)消息的數(shù)量。

當(dāng)數(shù)據(jù)收集請(qǐng)求到達(dá)區(qū)域代理節(jié)點(diǎn)后，區(qū)域代理節(jié)點(diǎn)將已采集好的數(shù)據(jù)生成數(shù)據(jù)包并將數(shù)據(jù)收集請(qǐng)求的傳播路徑反轉(zhuǎn)作為數(shù)據(jù)包傳遞給Sink的路徑。由此，數(shù)據(jù)包便可避免通過泛洪找中繼節(jié)點(diǎn)。一旦數(shù)據(jù)包到達(dá)Sink節(jié)點(diǎn)，這次傳輸就結(jié)束了，Sink繼續(xù)移動(dòng)準(zhǔn)備下一次收集。

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

3.1 實(shí)驗(yàn)背景

為Sink設(shè)計(jì)了4種不同的路線模型，如圖4所示。圖4(a)為波浪形曲線，用于檢測(cè)LAT協(xié)議對(duì)震蕩型路線的優(yōu)化效率；圖4(b)為線性，即Sink一直在向遠(yuǎn)離代理節(jié)點(diǎn)的方向移動(dòng)，此時(shí)的情況最為簡(jiǎn)單，數(shù)據(jù)只需沿著移動(dòng)Sink記錄的足跡s節(jié)點(diǎn)傳輸即可到達(dá)Sink；圖4(c)為當(dāng)路線中出現(xiàn)閉合回路時(shí)的情形，該種情況下Sink移動(dòng)一段時(shí)間后回到了原來的位置，這種情況也是LAT 算法效率最高的情況；圖4(d)描述的是Sink的路線為隨機(jī)時(shí)的圖形，次時(shí)的路線是圖4 (a)～ 圖4 (c)是3種路線的組合，隨機(jī)路線是最符合實(shí)際情況的路線模型。

圖4 4種路線模型

3.2 節(jié)點(diǎn)密度對(duì)路徑平均長(zhǎng)度的影響

網(wǎng)絡(luò)的大小設(shè)置為500 m×500 m，并依次在網(wǎng)絡(luò)中部署11×11個(gè)節(jié)點(diǎn)到20×20個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的通信半徑為60 m，得到如圖5所示的趨勢(shì)圖，其中橫坐標(biāo)為網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)，縱坐標(biāo)為相應(yīng)規(guī)模下數(shù)據(jù)傳輸?shù)钠骄窂介L(zhǎng)度。

由圖5可看出，隨著網(wǎng)絡(luò)密度的變大，圓形和線性模型中的平均路徑長(zhǎng)度均未發(fā)生變化，圓形路線下平均路徑長(zhǎng)度最短，因Sink在移動(dòng)一段時(shí)間后回到了原點(diǎn)，所以其只有兩個(gè)LAT 節(jié)點(diǎn)，且LAT 節(jié)點(diǎn)之間的距離小于節(jié)點(diǎn)的通信半徑，因此圓形模型下的平均路徑長(zhǎng)度最短；線性模型下的平均路徑長(zhǎng)度是最多的，這是因Sink沿直線行走，并未產(chǎn)生任何的回路，因而其所記錄的所有足跡節(jié)點(diǎn)均為L(zhǎng)AT節(jié)點(diǎn)，也即最終的數(shù)據(jù)傳輸路徑；隨著網(wǎng)絡(luò)密度的增加，波浪形曲線和隨機(jī)模型下的曲線平均路徑長(zhǎng)度并未單一的增加或減少，這是因節(jié)點(diǎn)的增加導(dǎo)致節(jié)點(diǎn)間距的變化，從而影響LAT節(jié)點(diǎn)間泛洪時(shí)的中繼節(jié)點(diǎn)的個(gè)數(shù)，最終導(dǎo)致路徑長(zhǎng)度的變化。

由圖5可看出，隨機(jī)路線下LAT協(xié)議的性能較好，但在文獻(xiàn)[10]所提的算法中，隨機(jī)路線下算法性能卻較差，這是因文獻(xiàn)[10]的算法是基于預(yù)測(cè)的，而隨機(jī)的路線又難以預(yù)測(cè)，因而表現(xiàn)不佳。

3.3 通信半徑對(duì)平均路徑長(zhǎng)度的影響

圖6所示為調(diào)整節(jié)點(diǎn)的通信半徑對(duì)平均路徑長(zhǎng)度的影響。由圖中可看出，圓形模型起先路徑中有3個(gè)節(jié)點(diǎn)，通信半徑增至40 m后下降為2個(gè)節(jié)點(diǎn)，這可能是因Sink的起始位置間的距離>35 m且<40 m，使得半徑增加后兩個(gè)節(jié)點(diǎn)在通信半徑內(nèi)從而避免了泛洪。波浪模型和隨機(jī)模型由于通信半徑的增加導(dǎo)致泛洪的減少?gòu)亩鴾p少總的路徑長(zhǎng)度，但顯然通信半徑的增加對(duì)線性模型并沒有任何作用，因線性中并未用到泛洪。

3.4 對(duì)網(wǎng)絡(luò)總能耗的影響

圖7為隨著通信半徑的增加，網(wǎng)絡(luò)整體能耗的變化趨勢(shì)，對(duì)于線性模型和圓形模型而言，網(wǎng)絡(luò)總能耗隨著通信半徑的增大而快速增加。但對(duì)于波浪和隨機(jī)模型，由于通信范圍變化和路徑長(zhǎng)度變化對(duì)網(wǎng)絡(luò)能耗的雙重影響，故本圖中在路徑長(zhǎng)度不變時(shí)，能耗是增加的，而一旦路徑長(zhǎng)度降低(通信半徑為40 m，55 m，75 m時(shí))，網(wǎng)絡(luò)能耗隨之減少。根據(jù)圖7，當(dāng)通信半徑設(shè)為40 m時(shí)，網(wǎng)絡(luò)的整體能耗最小。

圖6 改變節(jié)點(diǎn)通信半徑對(duì)平均路徑長(zhǎng)度的影響

圖7 改變通信半徑對(duì)網(wǎng)絡(luò)中總能耗的影響

4 結(jié)束語(yǔ)

本文提出了LAT協(xié)議，一種能有效避免回路追蹤Sink的路由協(xié)議。LAT通過Sink移動(dòng)時(shí)的路線彎曲角度的變化，篩選出一條沒有回路的從代理節(jié)點(diǎn)到移動(dòng)Sink節(jié)點(diǎn)的數(shù)據(jù)傳輸路徑。

實(shí)驗(yàn)結(jié)果表明，LAT協(xié)議可顯著減少傳輸路徑的平均長(zhǎng)度，并使網(wǎng)絡(luò)的能耗大幅降低，從而延長(zhǎng)網(wǎng)絡(luò)的生命周期，通過改變網(wǎng)絡(luò)的規(guī)模，節(jié)點(diǎn)的通信半徑，Sink的移動(dòng)路線模型等參數(shù)來觀察網(wǎng)絡(luò)性能的變化，以此判斷LAT協(xié)議在何種情況下能發(fā)揮出自身的優(yōu)勢(shì)。結(jié)果表明，當(dāng)Sink的移動(dòng)路線存在閉合回路時(shí)，可發(fā)揮最大的優(yōu)勢(shì)，且LAT協(xié)議在隨機(jī)路線模型下的表現(xiàn)也較為優(yōu)秀。因此，LAT協(xié)議的提出對(duì)于數(shù)據(jù)收集系統(tǒng)的發(fā)展和深入研究具有重要意義。之后，還將進(jìn)一步研究區(qū)域代理節(jié)點(diǎn)，將其收集到的數(shù)據(jù)進(jìn)行融合處理，以減少其在數(shù)據(jù)傳輸過程中消耗的能量。

[1] Haiyun L,Fan Y,Jerry C,et al. TTDD: Two-tier data dissemination in large-scale wireless sensor networks[J]. Wireless Networks , 2005,11(1-2):161-175.

[2] Naveen K P,Anurag Kumar.Relay selection for geographical forwarding in sleep-wake cycling wireless sensor networks[J].IEEE Transactions on Mobile Computing,2013,11(3): 475-488.

[3] Shuai Gao, Sajal K Das.Efficient data collection in wireless sensor networks with path-constrained mobile Sinks[J]. IEEE Transactions on Mobile Computing, 2011,10(4): 592-608.

[4] Yun Youngsang,Xia Ye. Maximizing the lifetime of wireless sensor networks with mobile Sink in delay-tolerant applications[J].IEEE Transactions on Mobile Computing, 2010,9(9): 1308-1318.

[5] Liu Xingcheng,Ma Zaili.Query processing in multi-user scenario for wireless sensor networks[J].IEEE Sensors Journal,2011,11(3): 2533-2541.

[6] Li Zhenjiang,Liu Yunhao.Exploiting ubiquitous data collection for mobile users in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,24(2): 312-326.

[7] 魏鵬,路贊贊.無線傳感器網(wǎng)絡(luò)分布式多傳感器目標(biāo)檢測(cè)[J].電子科技,2014,27(3): 143-146.

[8] 劉睿瓊,齊小剛,孫正海.基于節(jié)點(diǎn)位置的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].電子科技,2013,26(3):130-133.

[9] Liu Xinxin,Zhao Han.Sink trail:a proactive data reporting protocol for wireless sensor networks[J].IEEE Transactions on Computers, 2013,62(1): 151-161.

[10] Wu Xiuchao,Kenneth N Brown. Analysis of smartphone user mobility traces for opportunistic data collection in wireless sensor networks[J].Pervasive and Mobile Computing, 2013,9(6):881-891.

[11] Saim Ghafoor,Mubashir Husain Rehmani. An efficient trajectory design for mobile Sink in a wireless sensor network[J].Computers and Electrical Engineering, 2013,40(7):2089-2100.

[12] Hyung June Lee,Martin Wicke.Data stashing: energy-efficient information delivery to mobile Sinks through trajectory prediction[C].Stockholm: IPSN, 2010.

[13] Intanagonwiwat C,Govindan R,Estrin D. Directed diffusion:A scalable and robust communication paradigm for sensor networks[C].Egpt:Proceedings of the 6th Annual International Conference on Mobile Computing And Networking,2000.

[14] 張智超.基于不均等分層分簇的無線傳感器網(wǎng)絡(luò)協(xié)議[J].電子科技,2015,28(3): 83-86.

A loop Avoidance Tracking Protocol for Data Query in WSNs with Mobile Sink

XU Huifen, WU Chunxue, YANG Guisong

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093, China)

Wireless sensor networks are usually used to collect data from large-scale networks. In order to reduce the energy consumption, mobile Sink is often used to collect the sensing data. In this paper, we propose a loop avoidance tracking (LAT) protocol for data query in WSNs with mobile Sinks. In this protocol, the Sink node can avoid the node in the loops by comparing the changes of angles but reserve the nodes which are not on a loop, and thus the data will be transferred to the Sink on a shorter routing path. The simulation results demonstrate that the proposed protocol improves the query efficient and offers satisfactory performance in prolonging the network lifetime.

mobile Sink; data query; LAT protocol; loop avoidance

2016- 01- 17

上海智能家居大規(guī)模物聯(lián)共性技術(shù)工程中心資助項(xiàng)目(GCZX14014)

徐慧芬(1991-)，女，碩士研究生。研究方向：無線傳感器網(wǎng)絡(luò)。鄔春學(xué)(1964-)，男，博士，教授。研究方向：嵌入式與移動(dòng)計(jì)算，無線傳感器網(wǎng)絡(luò)。楊桂松(1982-)，男，博士，講師。研究方向：物聯(lián)網(wǎng)與傳感網(wǎng)，機(jī)會(huì)網(wǎng)絡(luò)。

10.16180/j.cnki.issn1007-7820.2016.11.040

TN926

A

1007-7820(2016)11-142-04