隐藏节点冲突的发现与研究

林城誉，李拥军，谢嵘

（1.华南理工大学数学学院，广州510641；2.华南理工大学计算科学与工程学院，广州510006）

0 引言

（1）无线传感网络

无线传感网络（Wireless Sensor Network）[1-2]是由某个监测区域用于监测风速、温度、湿度等一个个的传感器以一种自组织的形式组成的网络系统。无线网络的自组织性表现在每个传感器节点相互协调运作，每个节点地位平等。LR-WPAN[3]是IEEE 802.15.4 为无线传感网络制定的新标准[4]，与其他的为蓝牙、Wi-Fi 制定的无线网络协议相比，LR-WPAN 更具备短距离、低功耗的特性，更适用于低成本高利用率的场景。

LR-WPAN 使用CSMA/CA[5-6]机制，用于协调传感器节点在数据传输时的信道争用，该机制尽可能地降低了网络传输的功耗。对于准备传输数据的节点设备，会先监测目前的传输信道是否被其他节点占用，若空闲，会有一个延迟时间来避免若干个节点同时发出数据造成的冲突。然而，如果网络中节点数量增多，则会加重网络的负载、加大整个网络的节点关于信道争用的冲突，则整个网络的性能也会随之下降。对于传感节点的冲突，尤其是隐藏节点引起的冲突更值得去重视与解决。隐藏节点的冲突指的是若有两个节点是隐藏关系（不能感知到对方），则有一个节点在感知到信道空闲之后开始发送数据，而另一个节点同时也向其协调器发送数据，由于信道的半双工机制而引起数据传输的冲突。在网络系统中，每个节点随机分布，隐藏节点间的冲突发生几率高达41%。这种频繁发生在隐藏节点的冲突不仅会延迟数据包的传输到达时间，还会进一步降低整个系统的吞吐量和增加不必要的能量消耗。如何准确地发现节点的隐藏关系和有效地消除它们之间的冲突，是一个亟待解决的问题。文献[7-8]中提出一种分组策略，实时地采集节点间的冲突，根据节点的隐藏关系动态地划分为几个竞争冲突的组别，每个组内的节点只能在规定的时间片内向外传输数据，即使当前时间片内并没有其他组的节点在发送数据。

（2）ZigBee 局域网协议

ZigBee[9-10]是一种基于IEEE 802.15.4 标准的低功耗LAN 协议。它具有体积小，成本低，功耗低，数据传输率低的特点，是无线短程通信领域的典型协议。Zig-Bee 网络使用一个中心节点来协调整个网络的通信，需要一种类似路由器将本地协议转换为Internet 协议的功能。ZigBee 网络中主要环节在于每个设备分配到有效的相应的地址，主流的地址分配机制是Fang M 等人[11]提出的DAAM（Distributed Address Assignment Mechanism）机制，此机制在TI 协议栈中是默认配置的，且该算法可以根据参数定制不同级别的地址。

（3）Bloom Filter

判断数据是否存在，一般使用互斥的集合结构来对数据去重和常数时间地获取元素。随着数据规模的增大，集合的内存占用比例也逐渐增多，在其不是业务主功能的情况下，占用过多的内存显然是不合理的，Bloom Filter[12]就是一种减少内存占用，可以在元素不存在的情况下返回确定的不存在，而由于可能存在的哈希冲突，对于判断元素存在的情况会有误判的小几率。例如需要对URL 去重，使用多个哈希函数将URL映射到提前预估好的位数组中，将其位置置为1，若URL 在多个哈希函数映射之后在位数组中的位置都为1，则可以判定其为重复的。在Mutaf P 等人[13-14]的研究中，Bloom Filter 的误判率已经大大下降。

1 模型

本文讨论了在无线传感网络下，LR-WPAN 的CSMA/CA 机制在节点间传输数据的信道控制管理机制，指出其在节点数量增多的情况下，基于隐藏节点关系而出现的传输冲突对整体网络性能的重大损耗。本文基于此问题，考虑组建一个完整的ZigBee 局域网络，提供完善的中心节点路由功能，提出可行的分组策略和基于Bloom Filter 的非隐藏关系节点的存储方法，最终有效地解决了发生在隐藏节点间的冲突问题。

1.1 组建ZigBee网络

发现无线传感网络中的节点隐藏关系的冲突，首先需要组建一个ZigBee 网络。网络中的中心节点负责协调网络的各个节点，具有路由功能，管理子节点的入网。ZigBee 地址分配协议分配唯一的地址给加入的节点，具体地，ZigBee 地址分派公式如下：

其中An是以A 为父节点的第n 个子节点的地址，Cm是每个父节点拥有的子节点数，Lm是网络的最大深度,Rm是子节点当中有几个具有路由功能。

1.2 分组策略

在组建好的网络中，采用一种分组策略，可以快速地发现节点的隐藏关系和采取相应的措施解决冲突问题。基本策略阐述如下：中心节点依次从A1～An发送广播，收集每个子节点的响应信息，其中发送地址来自中心节点，接收范围为整个网络节点，数据包包含子节点的地址Ai。每次发送bcRequestAlive1～bcRequest-Aliven 标志检测子节点存活状态，使用centerBroadcastEnd 标志最后收集各个节点发生冲突的详情。具体地，当发送bcRequestAlivei 后，每个子节点会开始网络侦听，并且需要节点i 的广播应答。节点i 以广播的形式应答childBroadcastAlivei，与i 节点不为隐藏关系的其他所有节点会记录i 的存活状态，而与i 节点为隐藏关系的子节点则收不到i 的广播内容。中心节点收到i 节点的应答，再向所有节点广播centerBroadcastAlivei消息，标志i 节点存活的状态。与i 节点不为隐藏关系的节点在收到centerBroadcastAlivei 消息，确定与i 的非隐藏关系，在自己的nearbloomfilter 记录i 节点信息，相应的与i 节点存在隐藏关系的节点也可以确定。最后子节点收到centerBroadcastEnd 消息后，整理nearbloomfilter 记录，发送给中心节点。至此，中心节点可以确定节点间的非隐藏关系，按照算法对节点分组（一般不超过6 组），同时每个组i 会生成groupbloomfilteri记录组内节点地址。中心节点依次广播组序号和groupbloomfilter 到所有子节点broadcaseGroup（i,groupbloomfilteri），子节点确认自己所属的组别。每个子节点确认自己所属的分组，之后每个节点使用分组通讯，只在自己的分组所对应的时间片里发送报文。至此分组完成且有效解决隐藏关系节点间的冲突问题。

1.3 Bloom Filter数据压缩

每个传感器节点内存有限，分组策略中的每个节点的非隐藏关系节点数量在随机分布的无线传感网络中，对于每个节点来说是不均匀的，每个节点对非隐藏关系的存储而占用的内存也是不均匀的，有一定可能出现某些节点资源不足的情况，导致有些节点资源损耗过多，性能变差。而使用Bloom Filter 存储非隐藏关系的节点信息，对与所有子节点，其所占用的内存是明确的，不会出现某些节点需要消耗过多的内存。具体地，若网络中存在120 个节点，一个分组中就拥有80个节点，每个地址16 位，需要160 个字节，超过ZigBee协议传输帧关于最大字节只有127 字节的限制，而Bloom Filter 可以只使用100 字节，便能够充分记录组内节点。然而Bloom Filter 在节点数目少的时候并不占优势，这是可预见的。

1.4 节点通信的时间复杂度

在只有一个中心节点，N 个传感器节点的ZigBee 网络中，从分组策略中可以得知每个节点都生成nearbloomfilter 记录需要3N 次通信时间，中心节点接收到nearbloomfilter 则需要N 次通信时间，即在4N 次通信时间（复杂度为O（N））内完成存在隐藏关系节点的发现。

2 实验

2.1 关于隐藏节点冲突关系发现与收集在ZigBee协议下的仿真实验

ZigBee 网络初始化：首先选取中心节点作为整个网络的协调器，协调器检测信道并选取最佳信道。配置网络具体参数，分配当前网络的唯一标识符。

节点加入网络：初始化完成后，当前只有中心节点存在，当其他节点加入网络的时候，会选择自己感应到信号最强的节点作为父节点（刚开始是中心节点），加入成功后会获得一个一个网络地址。

本次实验使用20 个节点组成的ZigBee 网络进行仿真，假定每个节点最大侦听范围为500M，以中心节点为圆心，每个节点随机分布，如图1 所示。

每个节点被分配不同的地址，Bloom Filter 使用10字节存储非隐藏关系节点信息，在一轮centerBroadcastEnd 后，中心节获取记录所有非隐藏关系的节点并且分组如表1 所示。

图1 节点分布图

表1 分组

同时使用Bloom Filter 记录每个组的组内节点地址，子节点通过groupbloomfilter 确认自己是否在组中，分组图如2 图。

图2 最终分组结果图

2.2 实验结果说明与讨论

本次通过仿真实验，观察到每个节点的分布以及相应的分组情况。通过对每个节点的分组进行可视化，与实际节点是否为隐藏关系做比较，该分组算法正确地划分了节点。通过对每个节点记录数据所占用的内存进行数据分析，每个节点关于节点信息的记录所占用的内存是均衡的。在不使用Bloom Filter 的情况下，系统性能会有所下降。

3 结语

本文分析了隐藏节点在无线传感网络中的冲突问题，并具体阐述了一种分组算法，有效地划分隐藏节点的关系，同时使用Bloom Filter 的数据压缩功能进一步解决具体环境中某些节点负载不均衡的问题，整体上是一套解决由隐藏节点冲突导致系统性能下降的问题的可行方案。