基于節點度-限制的數據融合樹構建算法*

宋三華

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

無線傳感網絡WSNs(Wireless Sensor Networks)由大量的微型傳感節點組成[1-2],這些傳感節點具有感測、通信能力,進而實現對環境的監測目的。目前,WSNs已廣泛應用于軍事勘測、環境管理以及健康醫療等領域[3-4]。

由于WSNs中節點能量受到限制,如何降低網絡能耗成為WSNs的首要目標。依據文獻[5]研究表明,傳輸數據所消耗的能量占居節點能耗的大部分。因此,如何優化路由,減少數據傳輸量,進而降低能耗成為WSNs的研究熱點[6-8]。

數據融合是減少傳輸數據量的有效技術之一。因此,將數據融合與路由協議相結合可有效地減少數據傳輸量?，F存的路由協議可分為基于數據DC(Data-Centric)和基于地址AC(Address-Centric)的兩類協議[9]。

而基于數據融合樹的路由是DC路由典型代表。文獻[10]引用了基于貪婪遞增融合樹GITD(Greedy Incremental Tree Data),通過融合樹優化路由。研究結果表明,基于DC路由的能耗低于基于AC路由。文獻[11]引用根樹概念建立樹骨干網,利用簇頭輪換機制降低能耗。此外,文獻[12]提出了基于能耗的融合樹構建算法。該算法從網絡能耗決策路由。然而,這些算法多數是從能量角度構建融合樹,并沒有考慮了融合時延。

為此,本文提出基于節點度-限制的數據融合樹構建DC-DATC(Degree-Constrained-based Data Aggregation Tree Constructing)算法。DC-DATC算法從節點度角度構建融合樹,降低高節點度對數據融合時延的影響,同時優化融合樹,減少了網絡能耗。實驗結果表明,提出的DC-DATC算法有效降低網絡能耗和融合時延。

1 網絡模型

建立圖論G=(V,E)的無線傳感網絡,其中V為傳感節點集,E為邊集。同時假定傳感節點的傳輸距離為R。如果兩個節點i、j間的歐式距離‖i-j‖小于R,則它們間存在一條邊(i,j)∈E。

在DC的無線傳感網絡,將每個節點的整個壽命劃分為多個工作時期WP(Working Periods),且每個工作時期WP包含T個時隙。每個節點i隨機在從T個時隙中選擇一個時隙用于傳輸數據包或接收數據包。假定節點i所選擇的時隙表示為A(i),且這個時隙稱為節點i的活動時隙(Active time slot),而其他T-1個時隙為休眠時隙,如圖1所示。圖中描繪了3個工作時期WP,且每個WP內含5個時隙,即T=5,而節點i選擇的時隙為2。

圖1 基于DC的WSNs的工作時隙

假定每個節點僅有一個數據包要傳,且每個節點在它的活動時隙只能接收數據包,但是,它能夠在任何時隙發送數據。此外,假定節點能夠融合它的子節點的數據[13],并通過數據融合樹向它的父節點傳輸。所謂數據融合就是指將兩個或多個數據轉換成一個數據包。

此外,一個信宿節點s∈V能夠接收其他所有節點的數據,直到網絡內所有數據傳輸至信宿后,數據融合過程才結束。

2 問題描述

在給定圖論G=(V,E)中和一個信宿s∈V。假定Sk表示在工作時期WPk內傳輸數據的節點集,并且保證Sk內的數據發送節點不發生沖突。因此,一個數據融合分配就可形式化表述為:

(1)

式中:L表示數據融合時延。

DC-DATC算法就是在一定的約束條件下,最小化融合時延,分別如式(2)～式(4)所示:

MinimineL

(2)

(3)

Si∩Sj=φ, ?i≠j

(4)

將DC-DATC算法對節點u的安排表示為[tsch(u),p(u)],這表示節點u被安排工作時期tsch(u)內的A(p(u))時隙向它的父節點p(u)傳輸數據。

3 DC-DATC算法

DC-DATC算法目的在于節點度-限制的融合樹DCT(Degree-Constrained Aggregation Tree),進而消除高節點度對數據融合時延的影響。給定預設的節點度閾值α,數據融合樹中的每個節點的子節點數不大于α。這個參數α由環境決定[14]。然而,在節點密度不是足夠高的環境下,并非所有節點均能滿足節點度限制條件。為此,DC-DATC算法就試著減少融合樹中節點度高于α的節點數。

3.1 節點度對融合時延的影響分析

首先給出融合時延定義。本文將信宿接收網絡內所有節點數據所需的工作時期WP數定義為融合時延。

為了減少融合時延,融合樹應最大化在同一個時期內工作的節點數。而融合樹內高節點度的節點數越多,融合時延也就越大。原因在于:高節點度的節點越多,在同一時期內傳輸數據的節點數也就越少,這就增加了工作時期數,最終增加了融合時延。

3.2 基于節點度構建融合樹的具體過程

此外,DC-DATC算法主要由兩個階段構成:初始階段和主要階段。在初始階段,先構成初始的數據融合樹,然后,在主要階段進一步完善樹的構建。在闡述DC-DATC算法前,先引用以下變量:

①nn(u):節點u的鄰居節點數;

②ChS(u):在DCT樹中節點u的子節點集;

③nch(u):在DCT樹中節點u的子節點數;

④napc(u):節點u的可選父節點APC(Available Parent Candidates)數。若節點υ是節點u的一個鄰居節點,如果υ滿足以下兩個條件,則υ稱為u的APC。兩個條件:?在DCT樹中,υ沒有被選成為u的子節點;?nch(υ)<α;

⑤NAS(u):節點u的可選活動者集。NAS(u)是指被加到DCT樹后,能構建DCT的節點u的子節點。

⑥state(u):節點u的狀態。DC-DATC算法規定節點u有4種狀態:等待(WAIT)、活動(ACTIVATED)、監聽(LISTEN)和完成(COMPLETE)

此外,依據napc值,將網絡內所有節點劃分兩類:①特殊節點,如果napc(u)=1,則節點u稱為特殊節點;②普通節點,如果napc(u)>1,則節點u稱為普通節點。

3.3 初始階段

初始階段的過程如算法1所示。最初,所有節點處于WAIT狀態。特殊節點υ(napc(υ)=1)先向它的鄰居節點發送JOIN_REQ消息,請求加入DCT。JOIN_REQ消息包含了節點的ID號。一旦接收到JOIN_REQ消息,它的唯一鄰居節點u就是更新局部變量,并廣播JOIN_ACCEPT消息,如算法1的第Step 3至第Step 6所示。

圖2 DC-DATC算法的初始階段

圖3 算法1的執行主流程

一旦接收到JOIN_ACCEPT消息,節點υ就加入DCT,并將它的狀態修改成COMPLETE,如第Step 7至第Step 9所示。同時,如果nch(u)≥α,節點u的其他鄰居節點就它們的APC數減一。因為節點u不再是這些節點的APC。應當注意:在更新napc后(第Step 4或第Step 10),普通節點就成為新的特殊節點,然后再重復上述過程。算法1執行過程如圖3所示。

3.4 主要階段

主要階段的偽代碼如算法2所示。如果信宿s的所有鄰居節點已經被選為了信宿s的子節點,即DCT已經構成完畢,此時DC-DATC算法就停止,如第2行所示。否則的話,信宿s就成為第1個活動節點,然后就開始尋找它的子節點。當state(s)≠COMPLETE,DC-DATC算法工作如2所示。

圖4 DC-DATC算法的主要階段

活動節點u就向它的鄰居節點發送FIND_CHILD消息,尋找子節點。一旦從WAIT狀態的鄰居節點接收到JOIN_REQ消息,活動節點u就為將它的特殊鄰居節點的退避時間設為零,如第Step 13所示。對于普通鄰居,它的退避時間t(u,υ):

t(u,υ)=d(u)+sl(υ,u)+rand(0,1)+[nch(υ)×T]

(5)

式中:sl(υ,u)的定義如式(6)所示:

(6)

在整個退避時間內,如果u接收到來自υ的JOIN_CONFIRM消息,則u就取消退避時間t(u,υ),如Step 18所示。否則的話,一旦t(u,υ)到期,u就執行Procedure1,如算法2的Step 18所示。由于特殊節點的退避時間是零,特殊節點的鄰居節點總是被選為u的子節點。而對于u的普通鄰居節點υ,一旦t(u,υ)到期,u就選擇節點υ作為它的子節點,并將此節點加入NAS(u),因此,節點υ成為新的活動節點,如Procedure1的Step 4所示。

一旦產生了新的子節點后,節點u就更新nch(u),再向它的一跳鄰居節點發送JOIN_ACCEPT消息,其包含了它的子節點信息,如Procedure1的Step 1至Step 2所示。

為了滿足節點度的限制,節點u就將nch(u)與α進行比較。如果已選擇了新的活動節點,并且nch(u)=α,則節點u就停止子節點的選擇過程,然后再將自己狀態修改為LISTEN,如Procedure1 Step 5至Step 9所示。通過這種方式,保證節點u的度不大于α。然而,如果節點u沒有選擇任何新的活動節點,它將繼續執行子節點的選擇過程。

圖5 Procedure1的偽代碼

圖6 Procedure2的偽代碼

如果節點u不能找到任何活動節點,它就向它的父節點發送STUCK消息,請求父節點尋找新的活動節點,并將自己的狀態修改為COMPLETE,如算法2的Step 23至Step 25所示。一旦接收到來自活動節點u的JOIN_ACCEPT消息,處于WAIT狀態節點υ就加入DCT。Procedure2顯示節點υ加入DCT的過程。節點υ先向一跳鄰居節點發送JOIN_CONFIRM消息,其包含自己的ID和父節點的ID,進而告知鄰居節點,它已經選擇了父節點。

如果節點υ是特殊節點,由于它與鄰居節點沒有可選鏈路時,節點υ就將改變狀態,進入COMPLETE,不再參與樹構建。否則,如果節點υ是普通節點,它將成為新的活動節點,繼續構建DCT。

已接收到NAS集內所有節點發送的STUCK消息后,處于LISTEN狀態的節點就知道它的所選擇的活動節點不能再找到新的活動節點,如算法2的Step 35所示。因此,它將執行Procedure 3,進而尋找新的活動節點。節點就向它的一跳鄰居節點廣播FIND。如果沒有發現活動節點,它就通過發送STUCK消息尋找新的活動節點。如果信宿s已接收到來自NAS(s)內所有節點的STUCK消息,信宿s就改變狀態,進入COMPLETE狀態,并停止DCT算法。

圖7 Procedure 3的偽代碼

構建整個DCT的主要過程如圖8所示。首先執行初始階段,然后由信宿檢測是否有節點已成為自己的子節點。若是,結束算法;否則信宿作為活動節點,尋找子節點。產生了新子節點后,就相繼執行Procedure 1、Procedure 2和Procedure 3。

圖8 構建整個DCT的主要過程

4 性能分析

4.1 仿真參數

利用MATLAB建立仿真平臺,并分析基于DC-DATC算法性能。假定N個傳感節點分布于100 m×100 m的正方形區域,信宿位于區域邊界上。傳感節點傳輸距離R=25 m。

為了更好地比較基于DC-DATC的路由的性能,選擇基于GITD的路由[15]和基于AC路由[16]。主要考查算法的數據融合時延和網絡能耗。數據融合時延是指在一個工作時期內信宿s接收到所有節點數據的時間。每次實驗,獨立重復50次,取平均值作為最終的仿真數據。

4.2 數據分析

在本次實驗中,假定節點數N從70～120變化,且T=100。平均能量隨節點數變化曲線如圖9所示。所謂平均能量是指出現第1個失效節點時,網絡中剩余節點的平均能量。平均能量越高,說明能耗越不平衡。

圖9 平均能量隨節點數變化曲線

從圖9可知,AC路由的能耗不平衡,原因在于AC路由的中間轉發節點過多,這加大了能耗。當中間節點能量已消耗殆盡,而其他節點能量還很高。而GITDC和DC-DATC路由通過有效的數據融合樹傳輸數據,平衡了網絡能耗。

接下來,分析網絡壽命。網絡壽命是指第一傳感節點失效時間,實驗數據如圖10所示。

圖10 網絡壽命

從圖10可知,基于DC-DATC的路由的網絡壽命優于CA和GITDC路由。節點數越多,優勢越明顯。原因在于:基于DC-DATC路由通過DC-DATC樹,優化數據傳輸,減少了中間節點的參與,同時通過DC技術,降低了能耗。

最后,數據包傳輸時延,實驗數據如圖8所示。從圖11可知,提出的基于DC-DATC的路由的數據包傳輸時延最低,這進一步說明,通過DC-DATC構建的樹能夠有效地優化數據傳輸,使得數據包快速傳輸到信宿,進而降低了傳輸時延。

圖11 數據包傳輸時延

5 總結

本文針對無線傳感網絡的數據傳輸問題,展開分析,并提出基于節點度-限制的數據融合樹構建DC-DATC算法。DC-DATC算法從節點度角度構建融合樹,進而優化數據傳輸路線,減少了數據傳輸量,一方面平衡了網絡能耗,另一方面也中間節點傳輸的數據量。最終,通過平衡能耗,延長了網絡壽命。

[1] Rehman A,Abbasi A Z,Islam N,et al. A Review of Wireless Sensors and Networks Applications in Agriculture[J]. Compute Stand Interfaces,2014,36(2):263-270.

[2] Li Z,Wang N,Franzen A,et al. Practical Deployment of an in-Field Soil Property Wireless Sensor Network[J]. Compute Stand Interfaces,2014,36(2):278-287.

[3] 陳東海,李長庚. 基于簇頭功能分化的無線傳感器網絡成簇算法[J]. 傳感技術學報,2015,28(2):244-248.

[4] 門順治,孫順遠,徐保國. 基于PSO的非均勻分簇雙簇頭路由算法[J]. 傳感技術學報,2014,27(9):1281-1286.

[5] Akyildiz I F,Su W,Cayirci E. A Survey on Sensor Networks[J]. IEEE Commun. Mag,2013,40(8):102-114.

[6] Kang B,Kwon N,Choo H. Developing Route Optimization-Based PMIPv6 Testbed for Reliable Packet Transmission[J]. IEEE Access,2016,4(3):1039-1049.

[7] Incel O D,Ghosh A,Krishnamachari B. Scheduling Algorithms for Tree-Based Data Collection in Wireless Sensor Networks[C]//Theoretical Aspects of Distributed Computing in Sensor Networks. Berlin,Germany,2012:407-445.

[8] Kang B,Choo H. An SDN-Enhanced Load-Balancing Technique in the Cloud System[J]. J Supercomputing,2016,72(1):1-24.

[9] Kang B,Choo H. A Cluster-Based Decentralized Job Dispatching for the Large-Scale Cloud[J]. EURASIP J Wireless Commun Netw,2016,1(2):1-8.

[10] Fafoutis X,Mauro A D,Vithanage M D. Receiver Initiated Medium Access Control Protocols for Wireless Sensor Networks[J]. Comput Netw,2015,76(3):55-74.

[11] Kumar N,Misra S,Obaidat M S. Collaborative Learning Automata-Based Routing for Rescue Operations in Dense Urban Regions Using Vehicular Sensor Networks[J]. IEEE Syst J,2015,9(3):1081-1090.

[12] Kang B,Myoung S,Choo H. Distributed Degree-Based Link Scheduling for Collision Avoidance in Wireless Sensor Networks[J]. IEEE Access,2016,4(6):7452-7468.

[13] Jung S G,Kang B,Yeoum S,et al. Trail-Using Ant Behavior Based Energy-Efficient Routing Protocol in Wireless Sensor Networks[J]. Int J Distrib Sensor Netw,2016,1(7):1-8.

[14] Aldeer M,Howard R,Al-Hilli A. Minimizing Energy Consumption in Transmit-Only Sensor Networks Via Optimal Placement of the Cluster Heads[C]//Proc 8th Wireless of the Students,by the Students,and for the Students Workshop,2016:36-38.

[15] Razaque A,Elleithy K M. Low Duty Cycle,Energy-Efficient and Mobility-Based Boarder Node-MAC Hybrid Protocol for Wireless Sensor Networks[J]. J Signal Process Syst,2015,81(2):265-284.

[16] Han G,Dong Y,Guo H,et al. Cross-Layer Optimized Routing in Wireless Sensor Networks with Duty Cycle and Energy Harvesting[J]. Wireless Commun. Mobile Comput,2015,15(16):1957-1981.

[17] Madden S,Franklin M J,Hellerstein J M,et al. TAG:A Tiny Aggregation Service for Ad-Hoc Sensor Networks[J]. ACM SIGOPS OperSyst Rev,2012,36(2):131-146.