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

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

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

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