论文发表 | 论文范文 | 公文范文
最新公告:目前,本站已经取得了出版物经营许可证 、音像制品许可证,协助杂志社进行初步审稿、征稿工作。咨询:400-675-1600
您现在的位置: 新晨范文网 >> 通信论文 >> 无线电波传播论文 >> 正文

无线传感器数据收集时隙分配算法

定制服务

定制原创材料,由写作老师24小时内创作完成,仅供客户你一人参考学习,无后顾之忧。

发表论文

根据客户的需要,将论文发表在指定类别的期刊,只收50%定金,确定发表通过后再付余款。

加入会员

申请成为本站会员,可以享受经理回访等更17项优惠服务,更可以固定你喜欢的写作老师。

摘要:对数据收集时延进行研究,先将最小收集时延问题进行形式化表述,并建立目标函数;依据节点剩余能量,并结合克鲁斯卡尔(Kruskal)算法构成最小生成树;依据最小生成树分配数据收集时隙。实验数据表明:提出的时隙分配算法能够有效地降低收集时延,并降低了能耗。

关键词:无线传感器网络;数据收集;最小生成树;能耗;分配时隙

引言

收集数据是无线传感器网络(wirelesssensornetworks,WSNs)最基础的任务[1,2]。针对数据收集的WSNs,常将网络内所有传感节点构建为以基站为根的树结构(treestruc-ture)[3,4],也称为基于树的数据收集问题。根据节点融合数据,该问题可分为非融合数据收集和融合数据收集。在非融合数据收集中,基站直接接收所有节点发送的数据,并不采集任何融合措施。数据收集树(datacollectiontree,DCT)的中间节点比其后裔节点(descendants)需要更多传输时隙。原因在于,中间节点不仅要传输自己的数据,还要给其后裔节点转发数据。而在融合数据收集方案中,传感节点将其来自后裔节点的数据与自己的数据进行融合,再将这些融合数据传输至其父节点[5,6]。本文以WSNs内的非融合数据收集问题为研究内容。针对非融合数据收集问题,现存的分配算法主要关注于依据树结构,如何快速地将传感节点数据传输至基站,即以少的时隙数完成数据收集。如ZhaoW[7]提出基于Colouring的分配算法,已用的Colour数据等于用于数据收集的时隙数。文献[7]分析多个算法,如时隙分配、信道分配以及树构建。类似地,文献[8,9]研究数据收集的最低时延。为此,本文提出有效数据收集时隙分配算法。实验数据表明,提出的时隙分配算法能够有效地降低数据收集时延,并降低了能耗。

1约束条件及问题描述

1.1约束条件

用图G=(V,E)表述传感网络,其中,V为顶点集,E为边。若两节点在彼此的通信范围内,则这两个节点的通信链路就存在。假定网络内只有一个基站,并由此基站在每个抽样间隔内收集传感节点的数据。类似于文献[3,4],网络内节点以数据收集树DCT进行管理,即Tree=(VT,ET),并以基站为根。其中,VT=V,ETE。在每个抽样间隔内,假定传感节点以概率p产生一个传感节点数据包,然后再以多跳方式将数据包传输至基站。将时间划分为m个时隙,即t={TS1,TS2,…,TSm}。其中TSm表示最后一个时隙,在这个时隙内,基站可能从其后裔节点接收数据包。显然,m是要求收集所有数据的总的时隙数,其反映了数据收集过程的时延。此外,每个节点有足够大的缓存区,在转发数据前,能够缓存所接收的数据包。

1.2问题描述

本文对要解决的问题进行形式化表述。对于给定的树T,每个节点v要求多个发送时隙,用于传输自身的数据和转发其后裔节点数据。为了能够成功接收数据,所分配给节点的时隙要满足两个条件:1)所分配的时隙能够完成数据的传输;2)所分配的传输时隙无碰撞。具体而言,假定节点v所分配的时隙表示为ST(v),ST(v)需满足的两个条件为式中Ch(v)为节点v的孩子节点。式(1)规定ST(v)内时隙个数应大于其所有孩子节点所分配的时隙数之和。而式(2)规定,给节点v所分配的时隙就与其二跳邻居节点所分配的时隙没有交集,即无碰撞,其中,Cs(v)表示节点v的二跳邻居节点所分配的时隙数。本文要解决的问题就是给DCT内每个节点分配时隙,并减少数据收集时隙。假定,在每个抽样间隔内,每个节点均有感测数据要传输,为此,需要给每个节点分配时隙。而对于每个叶节点,只需要分配一个时隙用于传输自身数据。所谓叶节点就是指其无孩子节点,即

2时隙分配

用ti(v)表示节点v时隙集ST(v)内第i个时隙,且ST(v)内时隙以升序排列,ti(v)∈ST(v),1≤i≤|ST(v)|。由于每个节点均有数据包会传输,需要给网络内每个节点分配时隙。因此,以迭代方式工作,直到每个节点被分配了足够传输时延,即满足式(1)。在每次迭代,时隙分配以准备就序节点(readynode,RN)开始。所谓RN就是指它的后裔节点已全部分配了时隙。

2.1两类时隙

节点除了传输自己的数据外,还需转发孩子节点的数据。这两类数据均需要分配时隙。因此,可将时隙分为两类:1)用于节点传输自身数据的时隙,称为传输时隙。因此,在每个间隔,只需给节点分配一个时隙。据此,可在无碰撞条件下,尽可能早地给节点分配传输时隙。假定在第k次迭代,节点v的传输时隙stk(v)满足式(8)可知,分配给节点v的时隙不能与其二跳邻居节点所分配的时隙重复(t(Uy∈Cs(v)ST(y)))。并且是在ST(v)内选择一个最靠前的时隙作为传输时隙。2)转发时隙,用于转发来自后裔节点的数据。由于节点需要负责转发它的所有后裔节点数据,给节点分配的转发时隙就等于其后裔节点数。在每次迭代中,只给一个节点分配一个时隙,节点v所分配的时隙要在它的所有孩子节点分配完时隙后。假定它的所有孩子节点在k次迭代之前已分配了时隙,那节点v应在i>k次迭代分配转发时隙。因此,给节点v分配的转发时隙为式中t>max{stk(x),x∈Ch(v)}为所分配的时隙要在其孩子节点时隙后。先从子树开始分配时隙,先给叶节点分配,然后是此叶节点的父节点。以图1为例,假定节点u有3三个孩子节点{θ1,θ2,θ3),且每孩子节点以自己构建子树,且分别表示为T(θ1),T(θ2),T(θ3)。

2.2基于节点剩余能量的最小生成树

本文利用节点剩余能量作为边权重,再利用克鲁斯卡尔(Kruskal)算法[10]构建最小生成树。Kruskal算法是构建最小生成树的常用算法,是通过边权重产生最小连通图。其思路简述如下:先从E中选择权重最小的边,若该边的顶点在Γ中不同的连通分量上,则该边加入Γ中,否则丢弃。然后,再从E中选择权重最小的边,依次类推,直到所有顶点均连通在同一个拓扑图内。以图2为例,描述构建最小生成树的原理。图中标的数字表述节点剩余能量。如节点2的剩余能量为30。依据节点剩余能量计算边权重,每条边权重等于边的两端节点剩余能量之和。如由节点5和节点2构成的边,其边权重为20与30的和,即50。先从找到最大权重的边,即从它的一跳邻居节点选择剩余能量最大的节点作为父节点,然后构成一个最小生成树。此外,基站的剩余能量无限大,因此,节点1,2,3都将基站作为父节点。实际上,其为树的根节点。

2.3分配时隙的流程

先利用Kruskal算法构成生成树,然后给树中的每个节点分配时隙,分配过程的伪代码如下

3性能仿真

3.1仿真参数

引用NS3[11]网络仿真器建立仿真平台。考虑100个随机在分布于100m×100m区域。每个节点的通信半径为15m。100个节点内只有部分节点在每轮产生数据包,即产生数据包的概率p从0~1变化。同时,为了更好地分析本文所提出的时隙分配算法性能,选择TPO[7]作为参照,每次实验独立重复200次,并取平均值作为最终的仿真数据。

3.2数据分析

首先分析数据收集时延,实验数据如图3所示。其中,数据收集时延是指总共需要的时隙数。可知,提出的时隙分配算法的数据收集时延低于其他各算法。与TPO算法相比,提出的时隙分配算法的时延数平均降低了32.4%。原因在于,时隙分配算法能够依据Kruskal算法构建最小生成树,再依据此树分配时隙,减少了所分配的时隙数。接下来,分析节点能耗。引用文献[12]的Bluetooth4.1标准的能量模型,并假定每个节点中的初始能量为3J。能耗数据如图4所示。可知,提出时隙分配算法有效地降低了总体能量,原因在于分配算法利用节点剩余能量构建最小生成树,再依据最小生成树合理分配时隙,进而降低了能耗。与TPO算法相比,提出的时隙分配算法的能耗平均降低了约5.4%。

4结论

本文针对无线传感网络的数据收集时延问题,展开研究,并提出新的时隙分配算法,进而降低数据收集时延,同时减少节点能耗。利用克鲁斯卡尔算法建立最小生成树,再依据最小生成树分配时隙。实验数据表明,提出的分配算法能够合理地给节点分配时隙,并减少了节点能耗。

作者:白秋产 王亮明 单位:淮阴工学院

无线传感器数据收集时隙分配算法责任编辑:张雨    阅读:人次