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

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

?

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

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

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

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

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

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

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

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

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

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

1.1 移動 Sink

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

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

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

1.2 LAT 節(jié)點

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

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

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

2.1 LAT節(jié)點的判斷

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

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

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

圖1 LAT 角示意圖

圖2 移動路線為非回路時LAT角的比較

圖3 移動路線為回路時LAT 角的比較

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

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

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

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

3 仿真實驗

3.1 實驗背景

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

圖4 4種路線模型

3.2 節(jié)點密度對路徑平均長度的影響

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

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

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

3.3 通信半徑對平均路徑長度的影響

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

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

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

圖6 改變節(jié)點通信半徑對平均路徑長度的影響

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

4 結(jié)束語

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

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

[8] 劉睿瓊,齊小剛,孫正海.基于節(jié)點位置的無線傳感器網(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ù)工程中心資助項目(GCZX14014)

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

10.16180/j.cnki.issn1007-7820.2016.11.040

TN926

A

1007-7820(2016)11-142-04