一種采用定向天線的無線傳感器網絡拓撲控制算法*

魏振春,朱增璽,韓江洪,衛 星,趙 意

(合肥工業大學計算機與信息學院,合肥 230009)

?

一種采用定向天線的無線傳感器網絡拓撲控制算法*

魏振春*,朱增璽,韓江洪,衛 星,趙 意

(合肥工業大學計算機與信息學院,合肥 230009)

針對無線傳感器網絡實際應用中存在節點分布不均勻的情況,提出一種采用定向天線的無線傳感器網絡拓撲控制算法DATCA,算法充分利用了定向天線較高的能量效率及較強的干擾抑制等特性。本文利用有邊界的帕累托分布構建節點分布模型,OPNET仿真結果表明:DATCA算法在保證網絡連通性的同時,相比傳統拓撲控制算法顯著提高了網絡的性能。

無線傳感器網絡;區域判定;OPNET;定向天線;拓撲控制

隨著無線通信及傳感器技術的發展,無線傳感器網絡越來越廣泛應用于環境監測、建筑健康監測及智慧城市等領域[1]。相關研究表明無線傳感器網絡拓撲結構質量對網絡的性能有重大的影響,因此如何構建和維護一高效合理的網絡拓撲結構、降低節點能耗[2]、減少通信干擾及提高網絡傳輸性能是無線傳感器網絡所研究的關鍵問題之一[3]。

智能天線技術向微型化快速發展,為其應用于無線傳感器網絡中提供了可能[4]。靈活的波束控制、優良的能量效率、極強的干擾抑制能力及相比全向天線更大的通信半徑[3]是智能天線的重要特性。故而研究者們開始關注智能天線網絡拓撲控制方法的研究[5],文獻[6]提出了基于定向天線的拓撲控制算法CMPGA-DO。文獻[7]提出了基于定向天線的算法DABTC,通過調節發射功率和改變天線朝向對網絡進行拓撲控制。還有學者提出了異構自組織網絡的拓撲控制算法[8],如DRNG、DLSS和DLMST等,其思想是通過拓撲生成規則構建局部拓撲子圖,達到優化全局拓撲目的,采用定向天線可提高異構無線自組網的傳輸性能。以上研究大多基于節點分布均勻網絡,對分布不均網絡有很大的局限性。

針對WSN應用過程中節點分布不均的問題,利用定向天線信號覆蓋距離遠、通信干擾小等特性,給出了一種采用定向天線的無線傳感器網絡拓撲控制算法(DATCA:Topology Control Algorithm for WSN with Directional Antennas),算法相比傳統拓撲控制算法大幅度提高了網絡性能。

1 基于定向天線的網絡模型

1.1 模型提出

定向天線具有諸多優良的特性,使得越來越多的學者開始研究基于定向天線的無線傳感器網絡。如圖1所示。

圖1 全向天線及定向天線節點的WSN

針對定向天線網絡模型作出如下假設:

①所有節點皆為靜態同構節點,具有相同的最大發射功率及功率接收閾限;

②節點可獨立調節天線的發射功率及方向([0,2π]的隨機值);

③無線通信能耗采用自由度空間模型。

1.2 定向天線模型

假設WSN中所有傳感器節點均分布在二維平面,如圖2所示為定向天線的模型[9]。

圖2 定向天線模型

根據文獻[9]定向天線具有如下特性:

①全向偵聽信號及定向發送信號能力,并且可以感知信號接收的方向。

②可自主控制波束方向(θ,Φ)及發射功率。

1.3 通信鏈路模型及節點能耗模型

天線發送功率模型,根據文獻[10]可知接收方接收到的功率Pr與發送方發送功率Pt的關系為:

(1)

其中,Gt、Gr分別為發送方與接收方天線增益,λ為波長,L為系統損耗因子(L≥1),d為收發雙方距離。

易知,發送方與接收方通信所需的最小發送功率Pmin-t:

(2)

故由已知Pt、Pr及P0便可計算出Pmin-t。

天線能耗模型,文獻[11]假定節點發送射頻放大模塊的能耗為Erf/bit,其他電路能耗為Eproc/bit,發送能耗Eproc/bit,接收能耗Erx/bit,do、dd分別為全向天線和定向天線在功率Pact下的通信距離。

定向天線發送nbit的數據的能耗Ed:

(3)

全向天線發送nbit數據的能耗Eo為:

(4)

可見,全向天線發送相同大小的數據到同一個接收節點所消耗的能量遠遠大于定向天線。

2 基于定向天線的拓撲控制算法

2.1 問題的提出

無線傳感器網絡應用中,人們往往更關注信息較多的區域,常常會在該區域部署更多的監測節點,造成分布不均勻的場景。相關研究結果表明,傳統的拓撲控制算法對于節點分布不均的場景存在較大的局限性。

本文將不同節點密度區域區別對待,引出區域劃分的概念,根據文獻[11],網絡被平均分成M個簇,理想情況下M個簇要覆蓋整個網絡[12],要滿足:

(5)

2.2 基于定向天線的拓撲控制算法

在上文討論基礎上,計算鄰居節點數判定其屬于稠密區域或稀疏區域,對不同密度的區域采用分而治之的思想解決節點分布不均造成的傳統拓撲控制算法局限性等問題。基于定向天線的無線傳感器網絡拓撲控制算法DATCA具體步驟如下:

①節點u初始化發送功率P(u)=Pact-max(實際最大發射功率),(θ,Φ)=(2π,π),周期性以Pact-max通告HELLO消息,其中包含自身ID、能量狀態及Pact-max。對于接收到的其他節點v的HELLO消息,將節點v的ID、保存至本地接收鄰居節點集Nr(u)。

②節點u鄰居節點探測完成后,θ=π/2,隨機打開天線主波束Φ∈{π/4,3π/4,5π/4,7π/4},計算接收鄰居節點集Nr(u)的長度Neigh_Length,若Neigh_Length≥K(根據2.1節討論結果),則節點屬稠密區域DenseArea,否則節點屬稀疏區域ThinArea,設置自身區域類型。若自身區域類型為ThinArea的節點u是其Nr(u)中能量最大的節點,則以Pact-max周期性通告AREAHEAD消息(節點ID、能量信息及發送功率),宣布自身為區域頭結點;若區域類型為DenseArea,節點u以Pact-max周期性通告Hello消息,收集鄰居節點集Nr(u)。

③節點v收到的AREAHEAD消息,若其區域類型為ThinArea,且自身未屬于其他任何區域,則改變其天線方向對準節點u,并周期性以Pact-max回復AREAMEMBER消息(節點ID、能量狀態及發送功率),宣布其加入該區域;若其區域類型為DenseArea,則以Pact-max回復DenseNode消息。節點u接收到Hello消息,若區域類型為DenseArea,則獲取接收信號的功率依據式(2)計算Pmin(u,v),并將節點v的ID、能量狀態及按Pmin(u,v)遞增順序保存至本地接收鄰居節點集Nr(u)中,若區域類型為ThinArea,則丟棄。

④節點u接收到其他節點v發送的AREAMEMBER/DENSENODE消息,獲取接收信號的功率根據式(2)計算節點u與節點v的最小發送功率Pmin(u,v),并將鄰居節點v的ID(若為DENSENODE消息,則標記v為關聯節點)、能量狀態及計算的Pact-min(u,v)保存至本地發送鄰居節點集Nt(u),并按Pact-min(u,v)遞增排序。

⑤若節點v再次收到AREAHEAD消息,則節點v處于多個區域通信覆蓋范圍之內,為域間關聯節點,回復CONNECTNODE消息給區域頭節點,其中含自身ID、能量狀態及發送功率。

⑥區域頭節點u接收到節點v的CONNECTNODE消息后,將消息內容保存到域間關聯節點集ConnectNode(u,v)中。

⑦最多經過2Δt+ε+δ時間,區域劃分算法結束后(δ為區域劃分算法最長執行時間),節點u判斷其區域類型,若為DenseArea,則執行鄰居選擇過程,在其本地接收鄰居節點集Nr(u)中選取前K個節點的ID加入到標志信息中(若N(u)中節點數小于K,亦加入標志信息中),并周期性通告NEIGHTABLE消息(節點ID及Nr(u))。若為ThinArea,則域內成員節點v收集一跳鄰居節點集,待所有稀疏區域的節點的Nt(u)確定后,運行區域內MST算法,節點u選擇最優鄰居節點構建拓撲,并將其標識Nt(u)中,節點u選擇與Nt(u)中所有節點通信所需最小發射功率的最大值作為其實際最優發射功率Pact-opt(u)。

⑧節點u收到的節點v的NEIGHTABLE消息中若有u的ID,則將Nr(u)中節點v標志為對稱鄰居。

⑨稠密區的所有節點經過4Δt+ε+δ[13]時間后鄰居選擇處理結束,每個節點u以其Nr(u)中到距離最大的對稱鄰居所需的功率作為實際最優發射功率Pact-opt(u)。

2.3 算法理論證明與分析

2.3.1 網絡拓撲連通性證明

DATCA算法生成的拓撲圖連通性可分為稀疏區域及稠密區域拓撲結構圖的連通性。在稠密區域內按照K-Neigh算法進行拓撲構建及控制,有關K-Neigh算法連通性已有相關研究成果說明。此處僅證明稀疏區域內拓撲結構圖的連通性。

假設網絡中不存在物理孤立區域及節點,故劃分區域后的拓撲圖G0是連通的,則只需要證明由DATCA算法生成的子圖G的連通性。根據文獻[14]先給出如下定義:

定義1給定邊(u1,v1)和(u2,v2),權值函數P′定義如下:

P′(u1,v1)>p′(u2,v2)?P(u1,v1)>p(u2,v2)或

P(u1,v1)=p(u2,v2)&&max{id(u1),id(v1)}>max{id(u2),id(v2)}或

P(u1,v1)=p(u2,v2)&&max{id(u1),id(v1)}=max{id(u2),id(v2)}&&

min{id(u1),id(v1)}>min{id(u2),id(v2)}定義1說明了任意節點u以最小發射功率為權值構建的最小生成樹的唯一性。

定義2對于任意u,v(u,v∈V(G)),若u,v之間存在路徑(w0=u,w1,…,wm-1,wm=v),(wi?wi+1,(wi,wi+1)∈V(G)且(wi+1,wi)∈V(G),i=0,…,m-1,wk∈V(G),k=0,1,…,m),記為u?v。

定理1若初始拓撲結構圖G0連通則G連通。

證明DATCA算法生成的圖G由若干個稠密區用K-Neigh算法生成的拓撲圖和稀疏區MST算法生成的唯一最小生成樹通過關聯節點相連形成的圖。故只需證明單個區域內任意兩個節點對連通,則整個網絡連通。

對于單個區域內任意的節點對(u,v),有P(u,v)≤Pmax和P(u,v)>Pmax2種情況。

①對區域Local(u)中滿足條件P(u,v)≤Pmax的所有節點對(u,v),按權值遞增排序:P′(u1,v1)

以下將用數學歸納法證明u?v

(i)對于m=1時,對于權值最小的節點對(u1,v1),DATCA算法保證u1?v1,故而u1?v1。

(ii)假設對所有的m

(a)若uk?vk,則uk?vk。

(b)若uk→vk或vk→uk。不妨假設uk→vk,當uk運行MST算法后,一定能從G0中找到一條uk到vk的路徑:path=(w0=u,w1,…,wp-1,wp=v)。

由uk構建最小生成樹的唯一性可知,P′(ui,vi)

所以由歸納假設可得wi?wi+1,即對于path中任意的兩個節點都有路可達,則u?v。

②對于Local(u)中P(u,v)>Pmax的節點對(u,v),由于G0連通,故而在G0中存在路徑:path=(r0=u,r1,…,rp-1,rp=v)且P′(ri,ri+1)Pmax的節點對(u,v),有u?v。

③網絡模型假設中沒有孤立區域的存在,則對于任意的區域Local(u)都存在節點v∈ConnectNode(u,v)使得相鄰的區域彼此連通。

綜上所述,由①②③可得,當G0連通,?u,v(u,v∈V(G)),u?v,即G連通。

2.3.2 算法時間復雜度分析

DATCA算法分為區域判定、鄰居節點選擇及最優實際功率設置3個過程。

在節點區域劃分階段,每個節點只需要發送兩次通告信息,故此階段算法復雜度為O(n),而此過程中,節點需要將鄰居節點集N(u)中Pact-min(u,v)進行遞增排序,本文采用直接插入排序算法對此進行排序,因而此處算法復雜度為O(n2)。故而總的時間復雜度為O(n)+O(n2)。

拓撲優化階段,鄰居節點選擇及最優實際功率設置階段,稀疏區域內運行克魯斯卡爾算法,其時間復雜度為O(eloge)(e為圖的邊),最優實際功率設置,皆為線性運算,時間復雜度為O(n)。

綜上所述,DATCA算法的時間復雜度為O(n)+O(n2)+O(eloge)

3 算法仿真與性能分析

本文采用文獻[15]的有邊界帕雷托(Pareto)分布描繪節點分布模型。用OPNET進行仿真,仿真參數如表1所示。

表1 場景設定及參數初始化表

將DATCA算法嵌入到無線自組網通信協議棧的MAC層協議中[16],實現帶有拓撲控制的MAC協議。以下為wlan_mac進程模型,如圖3所示。

圖3 MAC層進程模型圖

該模型分為7個狀態,主要狀態實現的功能如下:

①INIT狀態負責網絡初始化設置。

②IDLE狀態負責判斷中斷事件類型,若信道空閑直接發送,否則進入幀間等待DEFER狀態;若TIMER1_INTRPT,收集鄰居節點,轉向GNR_HELLO狀態;若TIMER1_OUT或TIMER2_INTRPT,進入區域判定及子區域劃分階段,轉向GNR_HEAD狀態;若TIMER2_OUT或TIMER3_INTRPT,進入拓撲控制優化階段,轉向TC_PRCS狀態;若接收到消息RCDT_ARRIVAL,進入消息處理,轉向RCV_PRCS狀態;若TIMER3_OUT,進入功率設定階段,轉向POW_SET。

③GNR_HELLO狀態:用定時器TIMER1,時間為Δt1;生成TC/HELLO幀放入發送緩沖;在離散的時刻Δt1current、Δt1current+i、…、Δt1current+ε預設中斷事件Generate_HELLO,模擬在ε段時間內周期性發送TC/HELLO;完成后轉向IDLE。

④GNR_HEAD狀態:計算Nr(u)長度N_Length,若N_Length≥K則為DenseArea,反之為ThinArea;ThinArea區的節點若自身為Nr(u)中能量最大的點,啟動定時器TIMER2,時間為Δt2;生成TC/AREAHEAD幀放入發送緩沖;在離散的時刻Δt2current、Δt2current+i、…、Δt2current+ε預設中斷事件Generate_HEAD,模擬在ε段時間內周期性發送TC/AREAHEAD,宣告為區域頭結點,完成后轉向IDLE。

⑤TC_PRCS狀態:啟動定時器TIMER3,若為DenseArea區節點,選取Nr(u)中前K個鄰居,用定時器TIMER3,時間為Δt3,生成TC/NEIGHTABLE幀放入發送緩沖;在離散的時刻Δt3current、Δt3current+i、…、Δt3current+ε預設中斷事件Generate_NEIGH,模擬在ε段時間內周期性發送TC/NEIGHTABLE;若h為ThinArea區節點,探測對稱鄰近節點,發送HI消息,完成后轉向IDLE。

⑥RVC_PRCS狀態:

?若為HELLO消息,計算Pmin(u,v),并以其遞增排序將節點v信息保存至Nr(u);

?若為AREAHEAD消息,若為DenseArea區節點,回復DENSENODE消息,若為ThinArea區節點且AH_Count++<1,回復AREAMEMBER消息,若AH_Count++≥1,回復CONNECTNODE消息;

?若為DENSENODE或CONNECTNODE消息,按不同類型標記關聯節點;

?若為AREAMEMBER消息,保存成員節點信息至Nt(u)中;

?若為NEIBERTABLE消息,在Nr(u)中標記對稱鄰居節點;

?若為HI消息,回復ACK消息;

?若為ACK消息,記錄對稱鄰居節點信息至Nt(u)中。

⑦POW_SET狀態:若為DenseArea區節點,網絡中所有節點設置發送功率為各自鄰居節點集Nr(u)中到最遠的對稱節點所需的最小發射功率為其實際最優功率Pact-opt;若為ThinArea區節點,選擇與Nt(u)中所有節點通信的最小功率的最大值作為最優發射功率,完成后轉入IDLE狀態。

針對不同的網絡節點數規模:100、150、200、250及300,對DATCA、UDG-DATCA、K-Neigh[17]、UDG-K-Neigh[17]拓撲控制算法運行300S后節點的平均能耗進行對比,如圖4所示。

圖4 節點平均能耗對比

隨著節點數增多,節點間距離變小,故而節點通信半徑變小,節點能耗降低。對UDG-K-Neigh算法,當網絡節點數較小時,稀疏區域節點數更少,節點以最大的發射功率通信以覆蓋足夠多的鄰居節點以確保網絡連通,故而能耗最大。K-Neigh拓撲算法,當稀疏區域節點較少時控制數據包交互較多,節點平均能耗較大。DATCA算法,由于針對稀疏區域及稠密區域采用不同的處理策略,在稠密區域節點能耗相比UDG-K-Neigh及K-Neigh算法而言要小的多,稠密區域占了總體節點數目的80%,故而節點平均能耗最小。

針對節點數目為200,輔助測試路由協議為DSR仿真時間為600 s,源節點與目的節點皆隨機選取,DATCA、K-Neigh、UDG-K-Neigh拓撲控制算法網絡分組交付率仿真結果如圖5所示。

圖5 分組交付率對比

分組交付率是指目的節點接收的總數據包個數與源節點發送的總數據包個數之間的比值,其可以反映網絡的數據傳輸效率。當業務負載較低時,分組碰撞概率較小,路由開銷較小且鏈路比較穩定,各個拓撲控制算法對網絡性能影響較小,故分組交付率都接近100%。當網絡業務負載逐漸增大,節點競爭信道概率變大造成鏈路失效概率變大,所有拓撲控制算法對應分組交付率都呈下降趨勢。通過實驗發現,定向天線由于其波束的方向性,通信干擾相比全向天線而言較少,在同等網絡負載下,DATCA算法相比UDG-DATCA算法、K-Neigh算法及UDG-K-Neigh算法而言,通信干擾及鏈路失敗概率較小。從而減少了路由發現開銷,保證了DATCA算法具有較高的網絡分組交付率。

4 結論

DADTA算法有效利用了定向天線增益高,降低了節點發射功率,減少了信號干擾,提高了網絡傳輸能力。不同的區域采用不同的拓撲控制算法也比較合理,對問題分而治之,仿真發現,DATCA算法在節點能量效率及分組交付率等方面較其他算法而言均有了顯著的提高,在很大程度上改善了網絡的性能。但于此同時算法也存在一定的缺陷,因區域頭結點任務量大、節點移動、節點死亡等客觀因素造成的拓撲結構變化,故DATCA算法的動態適應能力有待進一步研究。

[1] Shen X,Wang Z,Sun Y.Wireless Sensor Networks for Industrial Applications[C]//Fifth World Congress on Intelligent Control and Automation,2004,4:3636-3640.

[2]崔海霞,黎文樓,丁志文.無線傳感器網絡中基于能量效率的分布式MAC協議[J].傳感技術學報,2010,23(1):104-109.

[3]Jakllari G,Luo W,Krishnamurthy S V.An Integrated Neighbor Discovery and Mac Protocol for Ad Hoc Networks Using Directional Antennas[J].IEEE Transactions on Wireless Communications,2007,6(3):1114-1024.

[4]Rzymowski M,Kulas L.Design,Realization and Measurements of Enhanced Performance 2.4 GHz ESPAR Antenna for Localization in Wireless Sensor Networks[C]//EUROCON 2013,2013:207-211.

[5]Subramanian A P,Lundgren H,Salonidis T,et al.Topology Control Protocol Using Sectorized Antennas in Dense 802.11 Wireless Networks[C]//17th IEEE International Conference on Network Protocols,2009:1-10.

[6]Namboodiri V,Gao L,Janaswamy R.Power Efficient Topology Control for Wireless Networks with Switched Beam Directional Antennas[C]//IEEE International Conference on Mobile Adhoc and Sensor Systems,2005,8:596.

[7]賀鵬,李建東,陳彥輝,等.Ad Hoc網絡中基于方向性天線的分布式拓撲控制算法[J].軟件學報,2007,18(6):1308-1318.

[8]Li N,Hou J C.Localized Topology Control Algorithms for Hetero-geneous Wireless Networks[J].IEEE/ACM Transactions on Networking(TON),2005,13(6):1313-1324.

[9]Kucuk K,Kavak A.Connectivity Analysis for Wireless Sensor Networks with Antenna Array Integrated Central Node[J].Wireless Personal Communications,2013,72(2):1361-1371.

[10]Rout R R,Ghosh S,Ghosh S K.Efficient Data Collection with Directional Antenna and Network Coding in Wireless Sensor Networks[C]//IEEE International Conference on Advanced Networks and Telecommuncations Systems(ANTS),2012:81-86.

[11]Hu Q S,Zhang S,Chen Y,et al.An Energy Balanced Clustering Routing Based on Voronoi-Graph[J].Journal of Chinese Computer Systems,2012,33(3):457-461.

[12]李方敏,黃燦,吳學紅.一種基于分簇的分布式無線傳感器網絡拓撲控制算法研究[J].傳感技術學報,2008,21(6):1055-1060.

[13]Blough D M,Leoncini M,Resta G,et al.TheK-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks[C]//Proceedings of the ACM MobiHoc,2003:141-152.

[14]王東,陳文斌,李曉鴻,等.自組網中基于自適應波束天線的拓撲控制算法[J].計算機研究與發展,2010,47(3):407-415.

[15]Mottola L,Voigt T,Picco G P.Electronically-Switched Directional Antennas for Wireless Sensor Networks:A Full-Stack Evaluation[C]//10th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks(SECON),2013:176-184.

[16]于凱,謝志軍,金光,等.基于功率控制的無線傳感器網絡MAC協議研究[J].傳感技術學報,2013,26(9):1297-1302.

[17]李曉鴻,張大方,陳文斌,等.一種基于隨機波束天線的自組網拓撲控制協議[J].計算機學報,2011,34(7):1342-1350.

魏振春(1978-),男,寧夏青銅峽人,合肥工業大學計算機與信息學院副教授。主要研究方向為物聯網、分布式控制和傳感器網絡,weizc@hfut.edu.cn;

朱增璽(1986-),男,陜西富平人,合肥工業大學計算機與信息學院碩士研究生,主要研究方向為無線自組織網絡、物聯網,lovehong0551@163.com;

韓江洪(1954-),男,江蘇南京人,合肥工業大學計算機與信息學院教授,博導。主要研究方向為網絡與通信、無線網絡、離散事件系統,hjh@ialab.hfut.edu.cn;

衛星(1980-),男,安徽合肥人,合肥工業大學計算機與信息學院講師。主要研究方向為物聯網工程、工業自動化控制、汽車電子,weixing@ialab.hfut.edu.cn;

趙意(1990-),男,安徽合肥人,合肥工業大學碩士研究生,主要研究方向無線傳感網、嵌入式系統、汽車電子,zhaoyi_hfut@163.com。

ATopologyControlAlgorithmforWSNwithDirectionalAntennas*

WEIZhenchun*,ZHUZengxi,HANJianghong,WEIXing,ZHAOYi

(School of Computer and Information,Hefei University of Technology,Hefei 230001,China)

In order to solve the maldistribution for wireless sensor network,Topology Control Algorithm for WSN with Directional Antennas,DATCA is proposed,Algorithm takes full advantage of high energy efficiency and directional antenna interference suppression characteristics.Pareto distribution model will be built to compare the effectiveness between DATCA and traditional topology control algorithms.Simulation on OPNET results show that,under the precondition of ensuring the network connectivity,DATCA improves the performance of network.

wireless sensor networks;regional assignment;OPNET;directional antennas;topology control

項目來源:國家國際科技合作專項項目(2014DFB10060);國家物聯網發展專項資金計劃項目(工信部科〔2012〕583號);安徽省國際科技合作計劃項目(1303063009)

2014-02-20修改日期:2014-05-12

10.3969/j.issn.1004-1699.2014.06.016

TN393

:A

:1004-1699(2014)06-0791-06