一種采用定向天線的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?

魏振春,朱增璽,韓江洪,衛(wèi) 星,趙 意

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,合肥 230009)

?

一種采用定向天線的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?

魏振春*,朱增璽,韓江洪,衛(wèi) 星,趙 意

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,合肥 230009)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)實(shí)際應(yīng)用中存在節(jié)點(diǎn)分布不均勻的情況,提出一種采用定向天線的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴―ATCA,算法充分利用了定向天線較高的能量效率及較強(qiáng)的干擾抑制等特性。本文利用有邊界的帕累托分布構(gòu)建節(jié)點(diǎn)分布模型,OPNET仿真結(jié)果表明:DATCA算法在保證網(wǎng)絡(luò)連通性的同時(shí),相比傳統(tǒng)拓?fù)淇刂扑惴@著提高了網(wǎng)絡(luò)的性能。

無(wú)線傳感器網(wǎng)絡(luò);區(qū)域判定;OPNET;定向天線;拓?fù)淇刂?/p>

隨著無(wú)線通信及傳感器技術(shù)的發(fā)展,無(wú)線傳感器網(wǎng)絡(luò)越來(lái)越廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、建筑健康監(jiān)測(cè)及智慧城市等領(lǐng)域[1]。相關(guān)研究表明無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)質(zhì)量對(duì)網(wǎng)絡(luò)的性能有重大的影響,因此如何構(gòu)建和維護(hù)一高效合理的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、降低節(jié)點(diǎn)能耗[2]、減少通信干擾及提高網(wǎng)絡(luò)傳輸性能是無(wú)線傳感器網(wǎng)絡(luò)所研究的關(guān)鍵問(wèn)題之一[3]。

智能天線技術(shù)向微型化快速發(fā)展,為其應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)中提供了可能[4]。靈活的波束控制、優(yōu)良的能量效率、極強(qiáng)的干擾抑制能力及相比全向天線更大的通信半徑[3]是智能天線的重要特性。故而研究者們開(kāi)始關(guān)注智能天線網(wǎng)絡(luò)拓?fù)淇刂品椒ǖ难芯縖5],文獻(xiàn)[6]提出了基于定向天線的拓?fù)淇刂扑惴–MPGA-DO。文獻(xiàn)[7]提出了基于定向天線的算法DABTC,通過(guò)調(diào)節(jié)發(fā)射功率和改變天線朝向?qū)W(wǎng)絡(luò)進(jìn)行拓?fù)淇刂啤＿€有學(xué)者提出了異構(gòu)自組織網(wǎng)絡(luò)的拓?fù)淇刂扑惴╗8],如DRNG、DLSS和DLMST等,其思想是通過(guò)拓?fù)渖梢?guī)則構(gòu)建局部拓?fù)渥訄D,達(dá)到優(yōu)化全局拓?fù)淠康?采用定向天線可提高異構(gòu)無(wú)線自組網(wǎng)的傳輸性能。以上研究大多基于節(jié)點(diǎn)分布均勻網(wǎng)絡(luò),對(duì)分布不均網(wǎng)絡(luò)有很大的局限性。

針對(duì)WSN應(yīng)用過(guò)程中節(jié)點(diǎn)分布不均的問(wèn)題,利用定向天線信號(hào)覆蓋距離遠(yuǎn)、通信干擾小等特性,給出了一種采用定向天線的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?DATCA:Topology Control Algorithm for WSN with Directional Antennas),算法相比傳統(tǒng)拓?fù)淇刂扑惴ù蠓忍岣吡司W(wǎng)絡(luò)性能。

1 基于定向天線的網(wǎng)絡(luò)模型

1.1 模型提出

定向天線具有諸多優(yōu)良的特性,使得越來(lái)越多的學(xué)者開(kāi)始研究基于定向天線的無(wú)線傳感器網(wǎng)絡(luò)。如圖1所示。

圖1 全向天線及定向天線節(jié)點(diǎn)的WSN

針對(duì)定向天線網(wǎng)絡(luò)模型作出如下假設(shè):

①所有節(jié)點(diǎn)皆為靜態(tài)同構(gòu)節(jié)點(diǎn),具有相同的最大發(fā)射功率及功率接收閾限;

②節(jié)點(diǎn)可獨(dú)立調(diào)節(jié)天線的發(fā)射功率及方向([0,2π]的隨機(jī)值);

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

1.2 定向天線模型

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

圖2 定向天線模型

根據(jù)文獻(xiàn)[9]定向天線具有如下特性:

①全向偵聽(tīng)信號(hào)及定向發(fā)送信號(hào)能力,并且可以感知信號(hào)接收的方向。

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

1.3 通信鏈路模型及節(jié)點(diǎn)能耗模型

天線發(fā)送功率模型,根據(jù)文獻(xiàn)[10]可知接收方接收到的功率Pr與發(fā)送方發(fā)送功率Pt的關(guān)系為:

(1)

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

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

(2)

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

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

定向天線發(fā)送nbit的數(shù)據(jù)的能耗Ed:

(3)

全向天線發(fā)送nbit數(shù)據(jù)的能耗Eo為:

(4)

可見(jiàn),全向天線發(fā)送相同大小的數(shù)據(jù)到同一個(gè)接收節(jié)點(diǎn)所消耗的能量遠(yuǎn)遠(yuǎn)大于定向天線。

2 基于定向天線的拓?fù)淇刂扑惴?/h2>

2.1 問(wèn)題的提出

無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中,人們往往更關(guān)注信息較多的區(qū)域,常常會(huì)在該區(qū)域部署更多的監(jiān)測(cè)節(jié)點(diǎn),造成分布不均勻的場(chǎng)景。相關(guān)研究結(jié)果表明,傳統(tǒng)的拓?fù)淇刂扑惴▽?duì)于節(jié)點(diǎn)分布不均的場(chǎng)景存在較大的局限性。

本文將不同節(jié)點(diǎn)密度區(qū)域區(qū)別對(duì)待,引出區(qū)域劃分的概念,根據(jù)文獻(xiàn)[11],網(wǎng)絡(luò)被平均分成M個(gè)簇,理想情況下M個(gè)簇要覆蓋整個(gè)網(wǎng)絡(luò)[12],要滿足:

(5)

2.2 基于定向天線的拓?fù)淇刂扑惴?/p>

在上文討論基礎(chǔ)上,計(jì)算鄰居節(jié)點(diǎn)數(shù)判定其屬于稠密區(qū)域或稀疏區(qū)域,對(duì)不同密度的區(qū)域采用分而治之的思想解決節(jié)點(diǎn)分布不均造成的傳統(tǒng)拓?fù)淇刂扑惴ň窒扌缘葐?wèn)題。基于定向天線的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴―ATCA具體步驟如下:

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

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

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

④節(jié)點(diǎn)u接收到其他節(jié)點(diǎn)v發(fā)送的AREAMEMBER/DENSENODE消息,獲取接收信號(hào)的功率根據(jù)式(2)計(jì)算節(jié)點(diǎn)u與節(jié)點(diǎn)v的最小發(fā)送功率Pmin(u,v),并將鄰居節(jié)點(diǎn)v的ID(若為DENSENODE消息,則標(biāo)記v為關(guān)聯(lián)節(jié)點(diǎn))、能量狀態(tài)及計(jì)算的Pact-min(u,v)保存至本地發(fā)送鄰居節(jié)點(diǎn)集Nt(u),并按Pact-min(u,v)遞增排序。

⑤若節(jié)點(diǎn)v再次收到AREAHEAD消息,則節(jié)點(diǎn)v處于多個(gè)區(qū)域通信覆蓋范圍之內(nèi),為域間關(guān)聯(lián)節(jié)點(diǎn),回復(fù)CONNECTNODE消息給區(qū)域頭節(jié)點(diǎn),其中含自身ID、能量狀態(tài)及發(fā)送功率。

⑥區(qū)域頭節(jié)點(diǎn)u接收到節(jié)點(diǎn)v的CONNECTNODE消息后,將消息內(nèi)容保存到域間關(guān)聯(lián)節(jié)點(diǎn)集ConnectNode(u,v)中。

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

⑧節(jié)點(diǎn)u收到的節(jié)點(diǎn)v的NEIGHTABLE消息中若有u的ID,則將Nr(u)中節(jié)點(diǎn)v標(biāo)志為對(duì)稱鄰居。

⑨稠密區(qū)的所有節(jié)點(diǎn)經(jīng)過(guò)4Δt+ε+δ[13]時(shí)間后鄰居選擇處理結(jié)束,每個(gè)節(jié)點(diǎn)u以其Nr(u)中到距離最大的對(duì)稱鄰居所需的功率作為實(shí)際最優(yōu)發(fā)射功率Pact-opt(u)。

2.3 算法理論證明與分析

2.3.1 網(wǎng)絡(luò)拓?fù)溥B通性證明

DATCA算法生成的拓?fù)鋱D連通性可分為稀疏區(qū)域及稠密區(qū)域拓?fù)浣Y(jié)構(gòu)圖的連通性。在稠密區(qū)域內(nèi)按照K-Neigh算法進(jìn)行拓?fù)錁?gòu)建及控制,有關(guān)K-Neigh算法連通性已有相關(guān)研究成果說(shuō)明。此處僅證明稀疏區(qū)域內(nèi)拓?fù)浣Y(jié)構(gòu)圖的連通性。

假設(shè)網(wǎng)絡(luò)中不存在物理孤立區(qū)域及節(jié)點(diǎn),故劃分區(qū)域后的拓?fù)鋱DG0是連通的,則只需要證明由DATCA算法生成的子圖G的連通性。根據(jù)文獻(xiàn)[14]先給出如下定義:

定義1給定邊(u1,v1)和(u2,v2),權(quán)值函數(shù)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說(shuō)明了任意節(jié)點(diǎn)u以最小發(fā)射功率為權(quán)值構(gòu)建的最小生成樹(shù)的唯一性。

定義2對(duì)于任意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若初始拓?fù)浣Y(jié)構(gòu)圖G0連通則G連通。

證明DATCA算法生成的圖G由若干個(gè)稠密區(qū)用K-Neigh算法生成的拓?fù)鋱D和稀疏區(qū)MST算法生成的唯一最小生成樹(shù)通過(guò)關(guān)聯(lián)節(jié)點(diǎn)相連形成的圖。故只需證明單個(gè)區(qū)域內(nèi)任意兩個(gè)節(jié)點(diǎn)對(duì)連通,則整個(gè)網(wǎng)絡(luò)連通。

對(duì)于單個(gè)區(qū)域內(nèi)任意的節(jié)點(diǎn)對(duì)(u,v),有P(u,v)≤Pmax和P(u,v)>Pmax2種情況。

①對(duì)區(qū)域Local(u)中滿足條件P(u,v)≤Pmax的所有節(jié)點(diǎn)對(duì)(u,v),按權(quán)值遞增排序:P′(u1,v1)

以下將用數(shù)學(xué)歸納法證明u?v

(i)對(duì)于m=1時(shí),對(duì)于權(quán)值最小的節(jié)點(diǎn)對(duì)(u1,v1),DATCA算法保證u1?v1,故而u1?v1。

(ii)假設(shè)對(duì)所有的m

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

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

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

所以由歸納假設(shè)可得wi?wi+1,即對(duì)于path中任意的兩個(gè)節(jié)點(diǎn)都有路可達(dá),則u?v。

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

③網(wǎng)絡(luò)模型假設(shè)中沒(méi)有孤立區(qū)域的存在,則對(duì)于任意的區(qū)域Local(u)都存在節(jié)點(diǎn)v∈ConnectNode(u,v)使得相鄰的區(qū)域彼此連通。

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

2.3.2 算法時(shí)間復(fù)雜度分析

DATCA算法分為區(qū)域判定、鄰居節(jié)點(diǎn)選擇及最優(yōu)實(shí)際功率設(shè)置3個(gè)過(guò)程。

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

拓?fù)鋬?yōu)化階段,鄰居節(jié)點(diǎn)選擇及最優(yōu)實(shí)際功率設(shè)置階段,稀疏區(qū)域內(nèi)運(yùn)行克魯斯卡爾算法,其時(shí)間復(fù)雜度為O(eloge)(e為圖的邊),最優(yōu)實(shí)際功率設(shè)置,皆為線性運(yùn)算,時(shí)間復(fù)雜度為O(n)。

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

3 算法仿真與性能分析

本文采用文獻(xiàn)[15]的有邊界帕雷托(Pareto)分布描繪節(jié)點(diǎn)分布模型。用OPNET進(jìn)行仿真,仿真參數(shù)如表1所示。

表1 場(chǎng)景設(shè)定及參數(shù)初始化表

將DATCA算法嵌入到無(wú)線自組網(wǎng)通信協(xié)議棧的MAC層協(xié)議中[16],實(shí)現(xiàn)帶有拓?fù)淇刂频腗AC協(xié)議。以下為wlan_mac進(jìn)程模型,如圖3所示。

圖3 MAC層進(jìn)程模型圖

該模型分為7個(gè)狀態(tài),主要狀態(tài)實(shí)現(xiàn)的功能如下:

①INIT狀態(tài)負(fù)責(zé)網(wǎng)絡(luò)初始化設(shè)置。

②IDLE狀態(tài)負(fù)責(zé)判斷中斷事件類型,若信道空閑直接發(fā)送,否則進(jìn)入幀間等待DEFER狀態(tài);若TIMER1_INTRPT,收集鄰居節(jié)點(diǎn),轉(zhuǎn)向GNR_HELLO狀態(tài);若TIMER1_OUT或TIMER2_INTRPT,進(jìn)入?yún)^(qū)域判定及子區(qū)域劃分階段,轉(zhuǎn)向GNR_HEAD狀態(tài);若TIMER2_OUT或TIMER3_INTRPT,進(jìn)入拓?fù)淇刂苾?yōu)化階段,轉(zhuǎn)向TC_PRCS狀態(tài);若接收到消息RCDT_ARRIVAL,進(jìn)入消息處理,轉(zhuǎn)向RCV_PRCS狀態(tài);若TIMER3_OUT,進(jìn)入功率設(shè)定階段,轉(zhuǎn)向POW_SET。

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

④GNR_HEAD狀態(tài):計(jì)算Nr(u)長(zhǎng)度N_Length,若N_Length≥K則為DenseArea,反之為ThinArea;ThinArea區(qū)的節(jié)點(diǎn)若自身為Nr(u)中能量最大的點(diǎn),啟動(dòng)定時(shí)器TIMER2,時(shí)間為Δt2;生成TC/AREAHEAD幀放入發(fā)送緩沖;在離散的時(shí)刻Δt2current、Δt2current+i、…、Δt2current+ε預(yù)設(shè)中斷事件Generate_HEAD,模擬在ε段時(shí)間內(nèi)周期性發(fā)送TC/AREAHEAD,宣告為區(qū)域頭結(jié)點(diǎn),完成后轉(zhuǎn)向IDLE。

⑤TC_PRCS狀態(tài):啟動(dòng)定時(shí)器TIMER3,若為DenseArea區(qū)節(jié)點(diǎn),選取Nr(u)中前K個(gè)鄰居,用定時(shí)器TIMER3,時(shí)間為Δt3,生成TC/NEIGHTABLE幀放入發(fā)送緩沖;在離散的時(shí)刻Δt3current、Δt3current+i、…、Δt3current+ε預(yù)設(shè)中斷事件Generate_NEIGH,模擬在ε段時(shí)間內(nèi)周期性發(fā)送TC/NEIGHTABLE;若h為ThinArea區(qū)節(jié)點(diǎn),探測(cè)對(duì)稱鄰近節(jié)點(diǎn),發(fā)送HI消息,完成后轉(zhuǎn)向IDLE。

⑥RVC_PRCS狀態(tài):

?若為HELLO消息,計(jì)算Pmin(u,v),并以其遞增排序?qū)⒐?jié)點(diǎn)v信息保存至Nr(u);

?若為AREAHEAD消息,若為DenseArea區(qū)節(jié)點(diǎn),回復(fù)DENSENODE消息,若為ThinArea區(qū)節(jié)點(diǎn)且AH_Count++<1,回復(fù)AREAMEMBER消息,若AH_Count++≥1,回復(fù)CONNECTNODE消息;

?若為DENSENODE或CONNECTNODE消息,按不同類型標(biāo)記關(guān)聯(lián)節(jié)點(diǎn);

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

?若為NEIBERTABLE消息,在Nr(u)中標(biāo)記對(duì)稱鄰居節(jié)點(diǎn);

?若為HI消息,回復(fù)ACK消息;

?若為ACK消息,記錄對(duì)稱鄰居節(jié)點(diǎn)信息至Nt(u)中。

⑦POW_SET狀態(tài):若為DenseArea區(qū)節(jié)點(diǎn),網(wǎng)絡(luò)中所有節(jié)點(diǎn)設(shè)置發(fā)送功率為各自鄰居節(jié)點(diǎn)集Nr(u)中到最遠(yuǎn)的對(duì)稱節(jié)點(diǎn)所需的最小發(fā)射功率為其實(shí)際最優(yōu)功率Pact-opt;若為ThinArea區(qū)節(jié)點(diǎn),選擇與Nt(u)中所有節(jié)點(diǎn)通信的最小功率的最大值作為最優(yōu)發(fā)射功率,完成后轉(zhuǎn)入IDLE狀態(tài)。

針對(duì)不同的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)規(guī)模:100、150、200、250及300,對(duì)DATCA、UDG-DATCA、K-Neigh[17]、UDG-K-Neigh[17]拓?fù)淇刂扑惴ㄟ\(yùn)行300S后節(jié)點(diǎn)的平均能耗進(jìn)行對(duì)比,如圖4所示。

圖4 節(jié)點(diǎn)平均能耗對(duì)比

隨著節(jié)點(diǎn)數(shù)增多,節(jié)點(diǎn)間距離變小,故而節(jié)點(diǎn)通信半徑變小,節(jié)點(diǎn)能耗降低。對(duì)UDG-K-Neigh算法,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較小時(shí),稀疏區(qū)域節(jié)點(diǎn)數(shù)更少,節(jié)點(diǎn)以最大的發(fā)射功率通信以覆蓋足夠多的鄰居節(jié)點(diǎn)以確保網(wǎng)絡(luò)連通,故而能耗最大。K-Neigh拓?fù)渌惴?當(dāng)稀疏區(qū)域節(jié)點(diǎn)較少時(shí)控制數(shù)據(jù)包交互較多,節(jié)點(diǎn)平均能耗較大。DATCA算法,由于針對(duì)稀疏區(qū)域及稠密區(qū)域采用不同的處理策略,在稠密區(qū)域節(jié)點(diǎn)能耗相比UDG-K-Neigh及K-Neigh算法而言要小的多,稠密區(qū)域占了總體節(jié)點(diǎn)數(shù)目的80%,故而節(jié)點(diǎn)平均能耗最小。

針對(duì)節(jié)點(diǎn)數(shù)目為200,輔助測(cè)試路由協(xié)議為DSR仿真時(shí)間為600 s,源節(jié)點(diǎn)與目的節(jié)點(diǎn)皆隨機(jī)選取,DATCA、K-Neigh、UDG-K-Neigh拓?fù)淇刂扑惴ňW(wǎng)絡(luò)分組交付率仿真結(jié)果如圖5所示。

圖5 分組交付率對(duì)比

分組交付率是指目的節(jié)點(diǎn)接收的總數(shù)據(jù)包個(gè)數(shù)與源節(jié)點(diǎn)發(fā)送的總數(shù)據(jù)包個(gè)數(shù)之間的比值,其可以反映網(wǎng)絡(luò)的數(shù)據(jù)傳輸效率。當(dāng)業(yè)務(wù)負(fù)載較低時(shí),分組碰撞概率較小,路由開(kāi)銷較小且鏈路比較穩(wěn)定,各個(gè)拓?fù)淇刂扑惴▽?duì)網(wǎng)絡(luò)性能影響較小,故分組交付率都接近100%。當(dāng)網(wǎng)絡(luò)業(yè)務(wù)負(fù)載逐漸增大,節(jié)點(diǎn)競(jìng)爭(zhēng)信道概率變大造成鏈路失效概率變大,所有拓?fù)淇刂扑惴▽?duì)應(yīng)分組交付率都呈下降趨勢(shì)。通過(guò)實(shí)驗(yàn)發(fā)現(xiàn),定向天線由于其波束的方向性,通信干擾相比全向天線而言較少,在同等網(wǎng)絡(luò)負(fù)載下,DATCA算法相比UDG-DATCA算法、K-Neigh算法及UDG-K-Neigh算法而言,通信干擾及鏈路失敗概率較小。從而減少了路由發(fā)現(xiàn)開(kāi)銷,保證了DATCA算法具有較高的網(wǎng)絡(luò)分組交付率。

4 結(jié)論

DADTA算法有效利用了定向天線增益高,降低了節(jié)點(diǎn)發(fā)射功率,減少了信號(hào)干擾,提高了網(wǎng)絡(luò)傳輸能力。不同的區(qū)域采用不同的拓?fù)淇刂扑惴ㄒ脖容^合理,對(duì)問(wèn)題分而治之,仿真發(fā)現(xiàn),DATCA算法在節(jié)點(diǎn)能量效率及分組交付率等方面較其他算法而言均有了顯著的提高,在很大程度上改善了網(wǎng)絡(luò)的性能。但于此同時(shí)算法也存在一定的缺陷,因區(qū)域頭結(jié)點(diǎn)任務(wù)量大、節(jié)點(diǎn)移動(dòng)、節(jié)點(diǎn)死亡等客觀因素造成的拓?fù)浣Y(jié)構(gòu)變化,故DATCA算法的動(dòng)態(tài)適應(yīng)能力有待進(jìn)一步研究。

[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]崔海霞,黎文樓,丁志文.無(wú)線傳感器網(wǎng)絡(luò)中基于能量效率的分布式MAC協(xié)議[J].傳感技術(shù)學(xué)報(bào),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網(wǎng)絡(luò)中基于方向性天線的分布式拓?fù)淇刂扑惴╗J].軟件學(xué)報(bào),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]李方敏,黃燦,吳學(xué)紅.一種基于分簇的分布式無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ㄑ芯縖J].傳感技術(shù)學(xué)報(bào),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]王東,陳文斌,李曉鴻,等.自組網(wǎng)中基于自適應(yīng)波束天線的拓?fù)淇刂扑惴╗J].計(jì)算機(jī)研究與發(fā)展,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]于凱,謝志軍,金光,等.基于功率控制的無(wú)線傳感器網(wǎng)絡(luò)MAC協(xié)議研究[J].傳感技術(shù)學(xué)報(bào),2013,26(9):1297-1302.

[17]李曉鴻,張大方,陳文斌,等.一種基于隨機(jī)波束天線的自組網(wǎng)拓?fù)淇刂茀f(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2011,34(7):1342-1350.

魏振春(1978-),男,寧夏青銅峽人,合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院副教授。主要研究方向?yàn)槲锫?lián)網(wǎng)、分布式控制和傳感器網(wǎng)絡(luò),weizc@hfut.edu.cn;

朱增璽(1986-),男,陜西富平人,合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院碩士研究生,主要研究方向?yàn)闊o(wú)線自組織網(wǎng)絡(luò)、物聯(lián)網(wǎng),lovehong0551@163.com;

韓江洪(1954-),男,江蘇南京人,合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院教授,博導(dǎo)。主要研究方向?yàn)榫W(wǎng)絡(luò)與通信、無(wú)線網(wǎng)絡(luò)、離散事件系統(tǒng),hjh@ialab.hfut.edu.cn;

衛(wèi)星(1980-),男,安徽合肥人,合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院講師。主要研究方向?yàn)槲锫?lián)網(wǎng)工程、工業(yè)自動(dòng)化控制、汽車電子,weixing@ialab.hfut.edu.cn;

趙意(1990-),男,安徽合肥人,合肥工業(yè)大學(xué)碩士研究生,主要研究方向無(wú)線傳感網(wǎng)、嵌入式系統(tǒng)、汽車電子,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

項(xiàng)目來(lái)源:國(guó)家國(guó)際科技合作專項(xiàng)項(xiàng)目(2014DFB10060);國(guó)家物聯(lián)網(wǎng)發(fā)展專項(xiàng)資金計(jì)劃項(xiàng)目(工信部科〔2012〕583號(hào));安徽省國(guó)際科技合作計(jì)劃項(xiàng)目(1303063009)

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

10.3969/j.issn.1004-1699.2014.06.016

TN393

:A

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