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

本站小编为你精心准备了无线传感器数据收集时隙分配算法参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

摘要:对数据收集时延进行研究，先将最小收集时延问题进行形式化表述，并建立目标函数;依据节点剩余能量，并结合克鲁斯卡尔(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结论

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

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