一种采用定向天线的无线传感器网络拓扑控制算法*

魏振春,朱增玺,韩江洪,卫 星,赵 意

(合肥工业大学计算机与信息学院,合肥 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