徐慧芬,鄔春學,楊桂松
(上海理工大學 光電信息與計算機工程學院,上海 200093)
?
帶有移動Sink的傳感器網絡回路避免跟蹤協(xié)議
徐慧芬,鄔春學,楊桂松
(上海理工大學 光電信息與計算機工程學院,上海 200093)
無線傳感器網絡通常被應用于收集大規(guī)模網絡中的傳感數據,這些收集工作由Sink完成。為了降低網絡內能量空洞產生的概率,延長網絡壽命,目前多采用移動Sink收集數據。文中提出了一種帶有移動Sink的數據收集協(xié)議。該協(xié)議中,Sink節(jié)點能根據相鄰足跡節(jié)點間坐標夾角的變化,有效回避掉那些回路上的足跡節(jié)點,而只保留非回路上的足跡節(jié)點。仿真實驗結果表明,LAT協(xié)議可顯著提升數據查詢效率,并有效延長了網絡壽命。
移動Sink;數據查詢; LAT協(xié)議;回路避免
無線傳感器網絡由大量價格低廉,處理能力較弱的傳感器節(jié)點組成,其應用范圍廣泛,從精密的軍事領域到傳感信息繁多的農業(yè)領域。這些網絡的規(guī)模通常較大,網絡中節(jié)點數量較多,所需采集的數據類型較多,數據量大,且呈現出分布式特征。
在無線傳感網中存在一個匯聚節(jié)點(Sink)用來收集傳感器節(jié)點感知到的數據[1-6]。當Sink是靜態(tài)時,傳感器節(jié)點會根據指定的位置將感知數據路由給Sink,但這樣會使Sink附近的傳感器節(jié)點能量快速消耗,造成能量黑洞,從而縮短網絡壽命。因而現在的研究中,Sink大多是移動的。但由于Sink的移動性,網絡中的普通節(jié)點不能獲得移動Sink的位置信息,無法進行數據傳輸[7-8]。
有研究者提出了根據Sink的移動軌跡預測進行數據傳輸的路由協(xié)議[9-11],但該種方法對于Sink軌跡的預測并不適用于實際情況且有移動的局限性[12]。因而,本文提出了一種基于移動Sink的數據查詢解決方法,當Sink需要查詢其所在區(qū)域的傳感信息時,首先就近指定一個區(qū)域代理節(jié)點,然后向該代理節(jié)點發(fā)送數據查詢請求。Sink完成數據查詢請求后繼續(xù)移動,并在之后的移動過程中每隔一段時間記一次足跡節(jié)點。隨著Sink節(jié)點的移動,雖其所標記的足跡節(jié)點的坐標連線完整的記錄了Sink的移動軌跡,但由于該移動軌跡的隨機性而不可避免的會出現路徑回路。通過采用LAT算法,可有效解決路徑回路的問題。
假設網絡中有大量隨機部署的傳感器節(jié)點以及一個或多個移動Sink節(jié)點。初始化網絡時,每個傳感器節(jié)點均分配了位置坐標。同時,網絡中的節(jié)點被劃分為以下類型:移動Sink節(jié)點,區(qū)域代理節(jié)點,足跡節(jié)點,LAT 節(jié)點以及普通節(jié)點。其中,區(qū)域代理節(jié)點和足跡節(jié)點均是由Sink節(jié)點指定的。
1.1 移動 Sink
網絡中的移動Sink節(jié)點具有強大的計算能力和存儲容量,Sink通過無線的方式和網絡中的其他節(jié)點交換信息。每個Sink配備有GPS模塊,因而可隨時獲得自身的位置信息。移動Sink節(jié)點可收集網絡中任何區(qū)域的傳感信息,當其移動至感興趣區(qū)域時,首先會廣播代理請求以指定一個代理節(jié)點。
收到廣播的傳感器節(jié)點若不是其他移動Sink的代理節(jié)點,則返回一個代理確認消息。Sink從收到的所有代理確認消息中選取距離自身當前位置最近的節(jié)點作為該區(qū)域的區(qū)域代理節(jié)點,然后向這一節(jié)點發(fā)送數據查詢請求包,包括所要收集數據的范圍,收集周期以及收集的數據類型。
Sink發(fā)送完數據查詢請求后即離開,其移動路線具有隨機性,并每隔一段時間記錄一次足跡。代理節(jié)點只負責收集數據,并不追蹤Sink的位置,因而數據的收集請求是由Sink主動發(fā)起的。
1.2 LAT 節(jié)點
定義1 LAT 節(jié)點是Sink通過LAT協(xié)議判斷后不在路徑回路上的足跡節(jié)點。
LAT 節(jié)點是足跡節(jié)點的子集,規(guī)定Sink最先記錄的兩個足跡節(jié)點直接標記為LAT節(jié)點。從第3個足跡節(jié)點開始,Sink每次記錄過足跡節(jié)點后,就會根據LAT協(xié)議判斷上一個足跡節(jié)點是否在回路上,若不在回路上,則認為該節(jié)點為LAT 節(jié)點;若該節(jié)點經判斷在回路上,則認為其不是LAT節(jié)點,并繼續(xù)判斷上一個已認證過的LAT 節(jié)點是否在回路上,若該LAT節(jié)點也在回路上,則認為其不再是LAT節(jié)點,由此遞歸判斷上一個LAT節(jié)點直到某個LAT節(jié)點不在回路上或只剩下區(qū)域節(jié)點仍為LAT節(jié)點。
2.1 LAT節(jié)點的判斷
為了能清楚描述LAT協(xié)議的工作機制,在此定義LAT角,并通過比較LAT角來判斷一個節(jié)點是否處于回路上。
定義2 LAT 角是所判斷節(jié)點與區(qū)域代理節(jié)點所在連線和所判斷節(jié)點與Sink當前位置所在連線形成的≤180°的夾角,圖1中∠1。
如圖2所示,D節(jié)點是Sink的當前位置,C是當前的帶判定節(jié)點也是上一個記錄的足跡節(jié)點,節(jié)點B是上一個已判定為LAT節(jié)點的節(jié)點,其中,∠1是判定節(jié)點B時的LAT角,∠2是節(jié)點C的LAT角。通過比較∠1和∠2的大小可判斷節(jié)點C是否在回路上。顯然,若∠1<∠2,則說明Sink的移動并未產生明顯的回路。此時,節(jié)點C成為LAT節(jié)點;若∠1>∠2,則說明Sink產生了明顯的回路,則節(jié)點C不能成為LAT節(jié)點,且要繼續(xù)判斷節(jié)點B是否依然是LAT節(jié)點。
圖1 LAT 角示意圖
圖2 移動路線為非回路時LAT角的比較
圖3 移動路線為回路時LAT 角的比較
2.2 Sink發(fā)送數據收集請求
當Sink需要收集數據時,停止移動,發(fā)出數據收集請求,并將此時所有的LAT節(jié)點添加到數據包中作為數據包的傳輸路徑。由于在選取LAT節(jié)點時篩選掉了一部分足跡節(jié)點,因而兩個相鄰的LAT節(jié)點間距可能超過節(jié)點的通信范圍。在此,采用定向泛洪的方法可解決這一問題。
定向泛洪對節(jié)點轉發(fā)數據的方向進行限制,不允許數據自由地向四面八方擴散[11]。節(jié)點收到定向泛洪數據包時,通過判斷自身是否在泛洪限制的角度范圍來決定是否轉發(fā)該數據包,這樣不但可快速找到目標節(jié)點,還可大量減少網絡中重復消息的數量。
當數據收集請求到達區(qū)域代理節(jié)點后,區(qū)域代理節(jié)點將已采集好的數據生成數據包并將數據收集請求的傳播路徑反轉作為數據包傳遞給Sink的路徑。由此,數據包便可避免通過泛洪找中繼節(jié)點。一旦數據包到達Sink節(jié)點,這次傳輸就結束了,Sink繼續(xù)移動準備下一次收集。
3.1 實驗背景
為Sink設計了4種不同的路線模型,如圖4所示。圖4(a)為波浪形曲線,用于檢測LAT協(xié)議對震蕩型路線的優(yōu)化效率;圖4(b)為線性,即Sink一直在向遠離代理節(jié)點的方向移動,此時的情況最為簡單,數據只需沿著移動Sink記錄的足跡s節(jié)點傳輸即可到達Sink;圖4(c)為當路線中出現閉合回路時的情形,該種情況下Sink移動一段時間后回到了原來的位置,這種情況也是LAT 算法效率最高的情況;圖4(d)描述的是Sink的路線為隨機時的圖形,次時的路線是圖4 (a)~ 圖4 (c)是3種路線的組合,隨機路線是最符合實際情況的路線模型。
圖4 4種路線模型
3.2 節(jié)點密度對路徑平均長度的影響
網絡的大小設置為500 m×500 m,并依次在網絡中部署11×11個節(jié)點到20×20個節(jié)點,節(jié)點的通信半徑為60 m,得到如圖5所示的趨勢圖,其中橫坐標為網絡中的節(jié)點個數,縱坐標為相應規(guī)模下數據傳輸的平均路徑長度。
由圖5可看出,隨著網絡密度的變大,圓形和線性模型中的平均路徑長度均未發(fā)生變化,圓形路線下平均路徑長度最短,因Sink在移動一段時間后回到了原點,所以其只有兩個LAT 節(jié)點,且LAT 節(jié)點之間的距離小于節(jié)點的通信半徑,因此圓形模型下的平均路徑長度最短;線性模型下的平均路徑長度是最多的,這是因Sink沿直線行走,并未產生任何的回路,因而其所記錄的所有足跡節(jié)點均為LAT節(jié)點,也即最終的數據傳輸路徑;隨著網絡密度的增加,波浪形曲線和隨機模型下的曲線平均路徑長度并未單一的增加或減少,這是因節(jié)點的增加導致節(jié)點間距的變化,從而影響LAT節(jié)點間泛洪時的中繼節(jié)點的個數,最終導致路徑長度的變化。
由圖5可看出,隨機路線下LAT協(xié)議的性能較好,但在文獻[10]所提的算法中,隨機路線下算法性能卻較差,這是因文獻[10]的算法是基于預測的,而隨機的路線又難以預測,因而表現不佳。
3.3 通信半徑對平均路徑長度的影響
圖6所示為調整節(jié)點的通信半徑對平均路徑長度的影響。由圖中可看出,圓形模型起先路徑中有3個節(jié)點,通信半徑增至40 m后下降為2個節(jié)點,這可能是因Sink的起始位置間的距離>35 m且<40 m,使得半徑增加后兩個節(jié)點在通信半徑內從而避免了泛洪。波浪模型和隨機模型由于通信半徑的增加導致泛洪的減少從而減少總的路徑長度,但顯然通信半徑的增加對線性模型并沒有任何作用,因線性中并未用到泛洪。
3.4 對網絡總能耗的影響
圖7為隨著通信半徑的增加,網絡整體能耗的變化趨勢,對于線性模型和圓形模型而言,網絡總能耗隨著通信半徑的增大而快速增加。但對于波浪和隨機模型,由于通信范圍變化和路徑長度變化對網絡能耗的雙重影響,故本圖中在路徑長度不變時,能耗是增加的,而一旦路徑長度降低(通信半徑為40 m,55 m,75 m時),網絡能耗隨之減少。根據圖7,當通信半徑設為40 m時,網絡的整體能耗最小。
圖6 改變節(jié)點通信半徑對平均路徑長度的影響
圖7 改變通信半徑對網絡中總能耗的影響
本文提出了LAT協(xié)議,一種能有效避免回路追蹤Sink的路由協(xié)議。LAT通過Sink移動時的路線彎曲角度的變化,篩選出一條沒有回路的從代理節(jié)點到移動Sink節(jié)點的數據傳輸路徑。
實驗結果表明,LAT協(xié)議可顯著減少傳輸路徑的平均長度,并使網絡的能耗大幅降低,從而延長網絡的生命周期,通過改變網絡的規(guī)模,節(jié)點的通信半徑,Sink的移動路線模型等參數來觀察網絡性能的變化,以此判斷LAT協(xié)議在何種情況下能發(fā)揮出自身的優(yōu)勢。結果表明,當Sink的移動路線存在閉合回路時,可發(fā)揮最大的優(yōu)勢,且LAT協(xié)議在隨機路線模型下的表現也較為優(yōu)秀。因此,LAT協(xié)議的提出對于數據收集系統(tǒng)的發(fā)展和深入研究具有重要意義。之后,還將進一步研究區(qū)域代理節(jié)點,將其收集到的數據進行融合處理,以減少其在數據傳輸過程中消耗的能量。
[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] 魏鵬,路贊贊.無線傳感器網絡分布式多傳感器目標檢測[J].電子科技,2014,27(3): 143-146.
[8] 劉睿瓊,齊小剛,孫正海.基于節(jié)點位置的無線傳感器網絡分簇路由協(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] 張智超.基于不均等分層分簇的無線傳感器網絡協(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)共性技術工程中心資助項目(GCZX14014)
徐慧芬(1991-),女,碩士研究生。研究方向:無線傳感器網絡。鄔春學(1964-),男,博士,教授。研究方向:嵌入式與移動計算,無線傳感器網絡。楊桂松(1982-),男,博士,講師。研究方向:物聯(lián)網與傳感網,機會網絡。
10.16180/j.cnki.issn1007-7820.2016.11.040
TN926
A
1007-7820(2016)11-142-04