基于Gabriel图的无线传感器网络的数据通信方法

摘要

本发明公开一种基于Gabriel图的无线传感器网络数据通信方法，主要解决现有技术中节点发射功率统一带来的能量浪费和通信干扰及对节点负载均衡考虑不足的问题，其实现方案是在最大功率拓扑MPG基础上结合Gabriel图对网络进行拓扑控制，调整节点发射功率，更新邻居节点集并得到候选节点集，形成网络数据通信拓扑，进而根据新的路径成本引进轮盘赌选择方法，以概率路由方式将数据经多跳传输给汇聚节点sink，并在网络某节点死亡或移动时及时维护数据通信拓扑，保证网络继续运行。本发明的数据通信方法能够有效地提高整个网络的能量使用效率，降低节点通信干扰，延长网络生存时间，可用于大规模无线传感器网络。

说明书

技术领域

本发明涉及无线通信技术领域，特别是无线传感器网络中基于拓扑控制的数据通 信方法，用于解决各节点通信范围盲目最大造成的能量消耗快和节点间干扰明显的弊 端，提高整个网络的能量利用效率，延长网络生存时间。

背景技术

无线传感器网络WSNs近年来备受关注，它集数据采集、数据处理和数据传输于 一体，是一种各学科高度交叉的综合性智能系统，有着广泛的应用前景。WSNs通常 由传感器节点和汇聚节点sink按照自组织的方式构成，传感器节点将采集到的数据按 照诸如多跳的方式选择路由传输给汇聚节点sink，后者进行进一步的处理。

传感器节点通常由电池供电，有限的电量决定了能量的使用效率对节点乃至整个 网络而言至关重要。从工作特点上看，传感器节点能量的使用主要包括信息采集、数 据处理和节点通信三方面。研究表明，节点间相互通信的能耗占节点能量消耗的绝大 部分，而通信过程中数据发送所需的能量又占了整个通信的绝大部分。根据上述特点， 研究者们分别提出了提高WSNs能量效率的方法、机制或协议。

经典的最小传输能量协议MTE中，节点选择距离自己最近的节点作为下一跳， 该协议简单，开销小，但靠近汇聚节点sink的节点一直充当路由中继者，节点间负载 不均衡。虽然每一次的数据传输所需能量得到了优化，但从长远来看，部分节点被过 度利用，整个网络生存时间反而缩短了。为了均衡节点的负载，研究者们将概率机制 引进到路由选取当中。概率路由主张每次路由选择的随机性，试图使各节点的能量下 降速度保持一致。传统概率路由协议以节点到其邻居的通信成本为依据，概率随机选 取节点作为下一跳。然而，由于对剩余能量信息关注不足，会出现部分节点剩余能量 较少而另一些节点剩余能量还较多的情况，剩余能量较少表明这些节点被选中的概率 比较大，如果它们继续以较大概率被选中的话，整个网络的生存时间会受到影响。鉴 于此，Jae-hwan Chang，Leandros Tassiulas在文献Maximum Lifetime Routing In  Wireless Sensor Networks(ATIRP Conf.，Mar.2000)中提出了新的路径成本定义方式，传 统概率路由是以节点到其邻居的通信成本作为路径成本的，而该文章作者同时考虑了 节点剩余能量信息，定义路径成本为通信成本和剩余能量的组合。不难想象，路径成 本是和通信成本成正比的，而和邻居节点剩余能量成反比。

此外，基于拓扑控制的方法效果显著，得到了广泛关注与研究。

拓扑控制的方法一般来说包括以下两种：一种是基于功率控制的，另外一种则是 采用分层措施。基于功率控制的方法是在满足连通覆盖基本要求的前提下，尽可能的 减小节点发射功率来提高能量效率，其实现途径有两种：一种是假定各节点具有相同 的发射功率，从整体上寻求适当的发射功率来满足上述性质；另一种方式是考虑各节 点的差异性，它们在最大发射功率范围内分别调整自身发射功率来实现上述目标。分 层的思想则是根据节点的邻接情况设法改变网络逻辑拓扑，通常的做法是按照簇结构 或者支配集的思想来分层。见文献：A Distributed Topology Control Technique for Low  Interference and Energy Efficiency in Wireless Sensor Networks，Tapiwa M.Chiwewe and  Gerhard P.Hancke，IEEE Transactions on Industrial Informatics，Vol.8，No.1，pp11-19， Feb.2012。

在功率控制的实现途径中，人们经常用到临近图。临近图中一些图满足连通、稀 疏等性质，从而符合第二种实现途径的基本思想，可以加以利用。比如Gabriel图，它 除了满足连通性、稀疏性外，功率扩展因子PSF为1，这就保证了两个节点在构造的 Gabriel图上可以找到和原图最低能耗相当的路径。文献An Energy-savingAlgorithm of  WSN based on Gabriel Graph(Wang Ke，Wang Liqiang，Cai Shiyu and Qu  Song.WiCOM′09 Proceedings of the 5th International Conference on Wireless  communications，networking and mobile computing，pp1-4，Sept.2009)中作者以最大GG 边为节点发射功率调整所要满足的通信半径，同时让数据的收发在生成的Gabriel图 上进行。这样每个节点可供选择的下一跳仅限于和其有GG边连接的节点，而不再是 最大通信范围内的所有邻居，减少了通信计算量以及通信干扰发生的几率，但下一跳 可选择余地的大大减小又使得节点被重复选择的几率上升，从而会加快整个网络的能 量消耗速度。

发明内容

本发明的目的在于针对上述已有技术的不足，提供一种基于Gabriel图的无线传 感器网络的数据通信方法，以打破基于临近图的拓扑控制数据的收发仅在所生成的临 近图上进行的限制，提高整个网络能量使用率，降低网络中通信干扰，满足大规模 WSNs的传输要求。

实现本发明的技术思路是：运行Gabriel图构造方法构造原始网络对应的Gabriel 图拓扑，将节点发射功率从统一最大分别调整到满足通信半径为最大GG边，以降低 数据发送的能耗以及节点间的通信干扰。采用概率路由的方式选取路由，按照轮盘赌 的思想，使候选节点被选为下一跳的概率与新的路径成本成反比，均衡节点能量消耗 速度。当节点死亡或移动引起拓扑变化时，涉及到的节点按照Gabriel图构造方法维 护网络拓扑结构，维持网络继续运行。其具体实现包括如下步骤：

(1)无线传感器网络WSNs中各节点以最大发射功率广播位置信息，并记录邻居 节点信息，构造初始邻接表，形成网络最大功率拓扑MPG；

(2)根据最大功率拓扑MPG，利用Gabriel图构造算法，形成网络的Gabriel图拓 扑；

(3)根据Gabriel图拓扑，形成数据通信拓扑结构：

(3a)节点i分别计算与Gabriel图拓扑下各邻居节点k间的距离，找出最大距离， 并调整自身发射功率，使其通信半径与该最大距离一致，以降低通信干扰；

(3b)节点i在调整后的新通信半径下通过发送与应答查询消息，确认并找出链 路非对称的邻居节点，并从邻接表中删除链路非对称的节点，得到链路对称的邻居节 点集N(i)；

(3c)节点i分别计算自己和各邻居节点k到汇聚节点sink的距离，选出那些距离 汇聚节点sink比自己近的节点作为自身候选节点集C(i)；

(3d)重复步骤(3a)-(3c)，直到网络中所有节点i都得到了邻居节点集N(i)和候 选节点集C(i)，从而形成网络的数据通信拓扑；

(4)在数据通信拓扑上，需要发送数据的节点将收集到的数据通过多跳的方式传 输到汇聚节点sink：

(4a)需要发送数据的节点u，按照轮盘赌选择方法从自身候选节点集C(u)中选 择下一跳节点j；

(4b)需要发送数据的节点u，广播信标消息告知邻居节点它所选出的下一跳节 点是j，各邻居节点收到该消息后，下一跳节点j外的邻居节点均采取休眠或短暂休 眠操作；

(4c)需要发送数据的节点u发送数据到下一跳节点j；

(4d)下一跳节点j收到数据后成为新的发送数据节点，再重复步骤(4a)-(4c)， 直到数据传输到汇聚节点sink；

(5)当某节点自身剩余能量不足以完成一次数据收发时，称该节点死亡；当发生 节点死亡或移动导致上述拓扑发生变化时，根据死亡或移动节点的位置信息，及时地 维护网络数据通信拓扑。

本发明具有如下优点：

1)本发明结合Gabriel图对WSNs进行拓扑控制，充分考虑了各节点的差异性， 不再设定所有节点具有统一的发射功率及通信半径，而是结合Gabriel图拓扑分别限 定各节点的通信范围，减小了节点数据收发的能耗，并降低了节点间的通信干扰；

2)本发明在Gabriel图拓扑的基础上构建了新的数据通信拓扑，克服已有方法的 数据收发仅在Gabriel图拓扑上进行的局限性，增加了各节点的邻居节点以及可供选 择的下一跳节点数目，从而避免个别节点被过度使用，均衡了节点的能量消耗速度；

3)本发明将轮盘赌选择方法引进到概率路由选择中，与最小传输能量协议MTE 以及传统概率路由协议相比，给出了更符合WSNs特点的路径成本定义，提高了下一 跳选择的合理性，有利于均衡节点负载，提高整个网络能量利用效率，并延长网络生 存时间；

4)本发明的Gabriel图拓扑的构建方法简单且易实现，即使不知道各节点的确切 位置信息，在网络最大功率拓扑MPG构建完毕后，可以利用现有的WSNs定位算法 确定各节点间的相对位置，从而可以完成Gabriel图拓扑的构建，保证本发明方法的 可行性。

附图说明

图1是本发明的整体流程图；

图2是本发明中各节点构建数据通信拓扑时的子流程图；

图3是本发明中需要发送数据的节点u将数据传输到汇聚节点sink的子流程图；

图4是本发明中需要发送数据的节点u发送给下一跳节点j的数据包格式；

图5是本发明方法在给定网络环境下仿真所生成的最大功率拓扑MPG与Gabriel 图拓扑；

图6是本发明与其他两种路由协议在给定网络环境下运行后的剩余能量对比图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明确，下面结合上述附图对本发明 的具体实施步骤做进一步描述。

参照图1，本发明基于Gabriel图的无线传感器网络的数据通信方法，包括以下步 骤：

步骤1：无线传感器网络WSNs中各节点构造初始邻接表，形成网络最大功率拓 扑MPG。

(1.1)网络中各节点以最大发射功率广播自身位置信息；

(1.2)节点i接收到邻居节点k的位置信息后，记录该位置信息并将k加入邻接表；

(1.3)重复步骤(1.2)，直到节点i将接收到位置信息的所有节点都加入邻接表，形 成节点i的初始邻接表；

(1.4)重复步骤(1.3)，直到网络所有节点都得到了初始邻接表，从而形成无线传 感器网络WSNs的最大功率拓扑MPG。

步骤2：根据最大功率拓扑MPG，结合Gabriel图的定义，利用Gabriel图构造算 法，形成网络的Gabriel图拓扑。

(2.1)节点i根据自己和邻居节点k的位置信息，计算以i和k二者连线为直径的圆 的圆心位置以及半径，该圆心位置位于二者连线中心，半径为节点i和k间距离的一 半；

(2.2)节点i计算上述圆心到其它邻居节点的距离，并判断该距离是否小于上述半 径，若小于则表示该圆形区域内有其他节点存在，根据Gabriel图的定义，节点i和k 之间不存在边，节点i从邻接表中删除邻居节点k；

(2.3)重复步骤(2.1)-(2.2)，直到节点i对所有邻居节点k都进行了上述操作后， 即完成了邻居节点集的更新；

(2.4)重复步骤(2.3)，直到网络中所有节点都进行了上述操作并更新了邻居节点 集，如此便形成了网络的Gabriel图拓扑。

步骤3：根据Gabriel图拓扑，各节点均调整发射功率并更新邻居节点集，从而确 定候选节点集，形成数据通信拓扑结构。

参照图2，本步骤的具体实施如下：

(3.1)节点i分别计算与Gabriel图拓扑下各邻居节点k间的距离，找出最大距离， 并调整自身发射功率，以降低通信干扰，具体步骤如下：

(3.1.1)最大通信范围内包含汇聚节点sink的各节点，比较自己到sink的距离和 (3.1)中求出的最大距离，找出二者较大值，并调整发射功率，使得通信半径与二者较 大值一致；

(3.1.2)对于汇聚节点sink不在其最大通信范围内的节点，则直接调整发射功率 使其通信半径与(3.1)中求出的最大距离一致；

(3.2)节点i在调整后的新通信半径下通过发送与应答查询消息，确认并找出链路 非对称的邻居节点，并从邻接表中删除链路非对称的节点，得到链路对称的邻居节点 集N(i)，以减轻介质访问控制MAC层的负担，便于处理，具体实施步骤如下：

(3.2.1)节点i在调整后的新通信半径下广播查询消息；

(3.2.2)邻居节点k收到节点i的查询消息，判断节点i是否在其邻接表中，若在 则表明节点i和k能够互相通信，它们之间链路对称，此时邻居节点k回复确认消息 告知节点i它们之间链路是对称的；

(3.2.3)在广播查询消息后的限定时间内，节点i若没有收到邻居节点k的确认消 息，则表明节点i和k之间链路非对称，节点i从邻接表中删除邻居节点k；

(3.2.4)重复步骤(3.2.2)-(3.2.3)，直到网络中所有节点都从邻接表中删除了链路 非对称的节点，并得到链路对称的邻居节点集；

(3.3)节点i从邻居节点集中选出那些距离汇聚节点sink比自己近的节点作为自 身候选节点集C(i)，具体实施步骤如下：

(3.3.1)若节点i的邻居节点只有一个，即|N(i)|＝1，则将该唯一的邻居节点作为 候选节点集，即C(i)＝N(i)；否则，执行步骤(3.3.2)；

(3.3.2)若汇聚节点sink是节点i的邻居，即sink∈N(i)，则将汇聚节点sink加入 节点i的候选节点集C(i)；

(3.3.3)节点i分别计算自己和各邻居节点k到汇聚节点sink的距离，若有邻居节 点k距离汇聚节点sink比节点i近，则将该邻居节点k加入到节点i的候选节点集C(i) 中；否则，执行步骤(3.3.4)；

(3.3.4)节点i比较邻居节点集N(i)中各节点的剩余能量，找出剩余能量最多的 节点作为自身候选节点集C(i)；当出现这种情况时，节点i在网络运行过程中需要及 时找出邻居节点集N(i)中剩余能量最多的节点并更新候选节点集C(i)；

(3.4)重复步骤(3.1)-(3.3)，直到网络中所有节点i都得到了邻居节点集N(i)和候 选节点集C(i)，从而形成网络的数据通信拓扑。

步骤4：在数据通信拓扑上，需要发送数据的节点将收集到的数据通过多跳的方 式传输到汇聚节点sink。

参照图3，本步骤的具体实施如下：

(4.1)需要发送数据的节点u，按照轮盘赌选择方法从自身候选节点集C(u)中选 择下一跳节点j，具体选择步骤如下：

(4.1.1)若需要发送数据的节点u发现汇聚节点sink属于自身候选节点集C(u)， 则直接选择sink作为下一跳j；否则，执行步骤(4.1.2)；

(4.1.2)若需要发送数据的节点u发现自身候选节点集C(u)中只有一个节点，即 |C(u)|＝1，则直接选取自身候选节点集C(u)中唯一的节点作为下一跳j；否则，执行 步骤(4.1.3)；

(4.1.3)需要发送数据的节点u分别计算它到候选节点集C(u)中各节点v的路径 成本及其倒数值，其中分母为归一化的剩余能量，E_v0表示候选节点集C(u)中 各节点v的初始能量，E_v表示候选节点集C(u)中各节点v的当前剩余能量；分子e_uv则 表示需要发送数据的节点u发送数据到候选节点集C(u)中各节点v需消耗的能量；

(4.1.4)需要发送数据的节点u计算步骤(4.1.3)中各倒数值的总和，并计算(4.1.3) 中各倒数值在总和中所占比例，将该比例作为候选节点集C(u)中各节点v的轮盘比 重；

(4.1.5)将上述比重逐个累加并依次保存相应累加值，形成累加值区间；

(4.1.6)随机生成(0，1)内的随机数并判断该随机数落在上述累加值区间的哪个区 间，则这一区间所对应的节点作为需要发送数据的节点u所选择的下一跳节点j；

(4.2)需要发送数据的节点u广播信标消息，下一跳节点j外的邻居节点均采取休 眠或短暂休眠操作，具体步骤如下：

(4.2.1)节点i广播信标消息，告知各邻居节点它所选择的下一跳节点为j；

(4.2.2)邻居节点k收到信标消息后，若k发现节点i不在自身邻接表中，说明节 点k和i之间链路非对称，则邻居节点k继续判断自己是否属于节点j的候选节点集 C(j)，若不属于则直接休眠直到下次数据发送，否则短暂休眠直到下一跳节点j开始 数据发送；否则，执行步骤(4.2.3)；

(4.2.3)邻居节点k收到信标消息后，若k发现节点i在自身邻接表中且k属于节 点i的候选节点集C(i)但自己不是下一跳节点j，即k∈C(i)但k≠j，则邻居节点k判 断自己是否属于节点j的候选节点集C(j)，若属于则短暂休眠直到下一跳节点j开始 数据发送，否则直接休眠直到下次数据发送；否则，执行步骤(4.2.4)；

(4.2.4)邻居节点k收到信标消息后，若k发现节点i在自身邻接表中且则k直接休眠直到下次数据发送；

(4.3)需要发送数据的节点u发送数据到下一跳节点j，节点u发送给下一跳节点 j的数据包格式如图4所示，该数据包包含了节点u的邻居节点集N(u)以及其中节点 的剩余能量信息，便于下一跳节点j更新自身各邻居节点的剩余能量信息，从而进行 轮盘赌选择，提高下一跳选择的准确性；

(4.4)下一跳节点j收到数据后成为新的发送数据节点，再重复步骤(4.1)-(4.3)， 直到数据传输到汇聚节点sink；

(4.5)各节点根据具体应用下数据收发的特点，或者定期广播自身剩余能量信息， 或者将自身剩余能量信息附到向汇聚节点sink传输的数据包中，以便于邻居节点及时 更新该节点剩余能量信息，提高轮盘赌选择的准确性。

步骤5：当发生节点死亡或移动导致上述拓扑发生变化时，根据死亡或移动节点 的位置信息，及时地维护网络数据通信拓扑。

(5.1)当节点i死亡，即节点i自身剩余能量不足以完成一次数据收发，或者节点i 移动时，它以最大发射功率广播信标消息，向邻居节点宣告自己死亡或者告知邻居节 点自己新的位置信息；

(5.2)接收到上述消息的邻居节点，将节点i从邻接表中删除或者记录节点i新的 位置信息，并按照Gabriel图构造算法更新邻接表；

(5.3)在步骤(5.2)的基础上，上述节点均按照(3.1)-(3.3)所述的步骤重新调整发射 功率，更新邻居节点集以及候选节点集；

(5.4)当汇聚节点sink移动时，所有网络节点结合新的sink位置信息，重新选出 那些距离sink比自己近的节点来更新候选节点集。

本发明的效果可以通过以下仿真进一步说明：

1.仿真条件

网络节点均匀分布在监测区域内，各节点定期将收集到的数据传输给汇聚节点 sink。简单起见，假定所有传感器节点都具有相同的初始能量，数据传输过程中不进 行数据融合且计算能耗不计，同时设定整个网络具有结合了时分多址TDMA技术的 理想的介质访问控制MAC协议，以保证各节点在介质访问控制MAC协议分配给自 己的时隙向汇聚节点sink发送收集到的数据，并且其他不相关的节点处于休眠状态。 最后，假定信道理想，数据和广播消息的收发不需要重传。

其它仿真参数如表1所示：

表1仿真参数

 区域field(meter×meter)   100×100  节点数目number of nodes   100  sink位置sink position   (0，0)  初始能量initial energy(J)   2  最大通信半径maximum transmission range(m)   25  数据包大小packet size(bits)   1000(MTE)or 1200(other)  信标消息大小beacon message size(bits)   100  查询消息大小query message size(bits)   50

2.仿真内容

仿真1，结合上述参数，生成网络最大功率拓扑MPG与Gabriel图拓扑，如图5 所示，其中图5(a)是网络最大功率拓扑MPG，图5(b)是网络Gabriel图拓扑。从图5(a) 与图5(b)的比较可以看出，Gabriel图拓扑保证了整个网络的连通性，同时，与最大功 率拓扑MPG相比，各节点邻居节点数目减少，有利于抑制数据的冗余传输并降低节 点间通信干扰。当各节点结合Gabriel图拓扑按照步骤3调整了通信范围后，节点发 送与接收数据的能量消耗减小，有助于提高整个网络的能量利用效率。

仿真2，结合上述仿真条件，对分别采用本发明、传统概率路由与最小传输能量 MTE协议的三种数据通信方案进行比较，分析同一网络条件下三种通信方案的节点 剩余能量消耗情况，结果如图6所示。

从图6可以看出，在采用最小传输能量MTE协议的数据通信方案中，当网络第 一个节点死亡时，网络中一半以上节点的剩余能量在1J以上，节点间剩余能量差异 性大；与之相对应，在采用传统概率路由的方案中，这种差异性有所缓和，而采用本 发明的方案各节点剩余能量差异最小。可见，采用本发明的方案与其他两种方案相比， 节点的能量消耗速度得到了更好的均衡，有助于合理高效的利用整个网络的能量，延 长网络生存时间。

以上所述仅为本发明的仿真验证，并不用于限制本发明，其它等同的技术方案也 属于本发明的范畴，本发明的权利保护范围由权利要求限定。

符号说明

WSNs：Wireless Sensor Networks  无线传感器网络

i：传感器节点i

k：传感器节点i的邻居节点k

u：需要发送数据的节点u

v：需要发送数据的节点u的候选节点集C(u)中的节点v

j：下一跳节点j

N(i)：节点i的邻居节点集

C(i)：节点i的候选节点集

C(j)：下一跳节点j的候选节点集

N(u)：需要发送数据的节点u的邻居节点集

C(u)：需要发送数据的节点u的候选节点集

GG：Gabriel Graph                    Gabriel图

MTE：Minimum Transmission Energy     最小传输能量协议

PSF：Power Stretch Factor            功率扩展因子

MAC：Media Access Control            介质访问控制

TDMA：Time Division Multiple Access  时分多址