一种基于工业无线网络的路由和资源分配算法

本文根据家族谱系中的称谓和关系，将其对应到树型结构中的节点和节点之间的关系。使得对网络拓扑和路由协议的描述更加清晰、方便、易于理解。
Root节点称为根节点，也叫祖先节点。以图1为例，与根节点直接相连的孩子节点统称为“第1代”(B、C、D节点)，“第1代”的孩子节点统称为“第2代”(E、F、H、I、J节点)，以此类推。根节点也称为“第0代”。节点的子树的根称为该节点“儿子”，相应地，该节点称为儿子的“父亲”。例如：A节点是B节点的父亲，B节点是A节点的儿子。同一个父亲的儿子之间互为“亲兄弟”，亲兄弟有排行顺序，称为“家内排行”。父亲节点位于同一代的节点之间互为“堂兄弟”。例如：F节点和H节点互为堂兄弟。堂兄弟有排行顺序，称为“族内排行”。节点与上一代的节点(除了自己的父亲节点以外)构成“叔侄”关系。例如：C节点为F节点的叔父，F节点为C节点的子侄。
2.2 拓扑结构的建立与路由协议
网络建立之初，当网络协调器上电后，根节点广播发出“子嗣发现”数据包，其中包含发送节点的层变量(level=0)和节点ID。根节点的邻居节点接收到根节点发出的“子嗣发现”数据包后，将自己的层变量设置为1(level=1)，即确定自己为“第1代”中的一员；同时，“第1代”需要向父节点发送一个“父子关系确认”数据包(包含节点自身ID)，发送时间根据节点ID适当延迟，以避免碰撞。然后，“第1代”的节点继续广播“子嗣发现”数据包。没有确定层变量的节点在收到“第i代”节点的“子嗣发现”数据包后，记录发送方的ID，将自己的层变量设置为(i+1)，并回复“父子关系确认”数据包。这个过程蔓延下去，直到网络内的所有节点都被赋予一个层变量值，属于家族树中的某一代，拥有唯一的父节点和若干子节点。在家族树的建立过程中，父节点在收到所有子节点发来的确认报文后，需要广播一个“长幼顺序”数据包，其中包含所有子节点的排列顺序。子节点收到“长幼顺序”数据包后，记录自己的在兄弟中的排行，也就是“家内排行”。数据包的交互过程如图2所示。

由于网络的树型结构需要通过数据报文被不断传播，本协议还设计了一种具有针对性的树型结构线性存储方式。该存储方式结构清晰，所占空间较小，便于节点设备在本地存储自己的子树结构，以及将自己的子树结构以数据报文的形式发送出去。其数据格式如图3所示，数据举例部分依据图1的网络结构，根节点的ID为13，其余节点的ID以字母顺序编号。当一个子节点接收到其所有子节点发送的“子树报告”数据包后，它应组织一个包含自己所有子树的“子树报告”数据包发送给父节点。

3 基于工业无线网络的通信资源分配算法
3.1 信道与时隙的分配原则
由于无线传感器网络的通信特点，不同设备在相互通信时存在干扰。要想同时通信，相邻层之间不可分配相同的信道。对于信道的分配，可以设置n层作为一个信道重复周期。假设n=3，如图4所示，Root节点与第1代通信使用ch1信道，第1代与第2代通信使用ch2信道，第2代与第3代通信使用ch3信道，第3代与第4代通信可以重复使用ch1信道，如此循环。
由于无线传感器网络中的节点一般只装备一套射频装置，所以节点之间进行单播通信时需要分时。
父节点可以向所有子节点发送广播报文，例如：时间同步报文、数据查询报文等。如果不同父节点发送的广播报文覆盖范围重合，子节点在接收时就存在干扰，需要分时。如图4所示，节点1的广播范围覆盖节点4、5，节点2的广播范围覆盖节点6，则节点5和节点6不能同时接收父节点发送的广播报文。在家族树结构中，需要分时通信的情况还包括：父节点相同的节点在与其父节点通信时，需要分时；存在干扰的堂兄弟节点在与其父节点通信时，需要分时。

3.2 通信资源的分配算法

若同一代的节点发送广播报文的覆盖范围都重合，并且堂兄弟节点在与其父节点通信时均存在干扰，以图4的拓扑结构为例，资源的分配结果如图5(a)所示；若同一代的节点发送广播报文的覆盖范围都重合，而堂兄弟节点在与其父节点通信时均不存在干扰，以图4的拓扑结构为例，资源的分配结果如图5(b)所示。

4 仿真实验及分析
仿真实验在OMNet++平台上进行，拓扑采用8×8的Mesh结构，64个节点中包含一个网络管理者，负责全网络通信资源的分配。实验节点以中科院自主设计的GAINS-2节点为原型，该节点与Mica2节点兼容。节点的微控制器采用Atmega128L，射频芯片采用CC1000。网络协议用Visual C++开发，网络拓扑由.ned文件生成。
在网络正常监控阶段，当用户端有查询任务时，查询报文将沿着网络的拓扑结构传播。图6为模拟系统随机生成的网络拓扑以及路由协议建立的树型结构。查询任务一般具有周期性，沿网络的梯度方向传播。