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

随着半导体、微电子、通信和计算机技术的飞速发展，无线传感器网络技术取得了巨大的进步。由于无线传感器网络能够获取多种客观物理信息，已被应用在军事国防、工农业控制、城市管理、生物医疗、环境监测、抢险救灾等诸多领域。尤其是在恶劣环境下的工业现场设备监测(如大型工厂的冶金设备监测、绵延数千公里的输油管道监测和巨型船舶测试场的监测等)是近年来的研究热点[1]。
在无线传感器网络中，路由协议负责将数据分组从源节点通过网络转发到目的节点。路由的关键是要寻找源节点到目的节点间通信延迟较小的路径，提高整个网络的利用率，避免通信拥塞并均衡网络流量。传感器网络的路由机制经常与数据融合技术一起应用，通过减少通信量来节省能量。WIA-PA工业无线标准规定[2]：设备在加入网络后，各个路由设备通过发送信标帧来分配通信资源。信标帧中含有路由设备自身的超帧结构信息。超帧是一种用来组织网络通信时间分配的逻辑结构。超帧机制要求通信设备之间的时间精确同步，而时间信息的传播依赖于网络的路由。路由的实现离不开网络管理者对通信资源的分配，通信资源的分配效率将直接影响网络各方面的性能。
1 相关研究
1.1 无线网络的路由协议
随着无线传感器网络技术的发展，出现许多专门针对无线传感器网络的路由协议。根据应用目标的不同，这些路由协议大致可分为四种类型：能量感知路由协议、基于查询的路由协议、地理位置路由协议和可靠路由协议。
能量感知路由主要是根据节点的可用能量(剩余能量)或传输路径上的能量需求，选择数据的转发路径。为了均衡消耗整个网络的能量，SHAH R C.等人提出了一种能量多路径路由机制[3]。其核心思想是在源节点和目的节点之间建立多条路径，根据路径上节点的通信能耗以及节点的剩余能量，给每条路径设置一个被选择的概率，将通信能耗分散到多条路径上，延长网络的寿命。
定向扩散是一种基于查询的以数据为中心的路由机制[4]。汇聚节点根据应用需求，广播兴趣消息启动路由建立过程。中间节点通过兴趣表建立从数据源到汇聚节点的数据传输梯度，自动形成数据传输的多条路径。在这多条路径中，使用路径加强机制生成一条优化的数据传输路径。基于查询的路由协议还有适用于数据传输量较小的传感器网络的谣传路由等。
在某些应用中，节点需要获取它的位置信息，如森林防火。地理位置路由假设节点已知自己的地理位置信息，以及目的节点或目的区域的地理位置，并依据这些地理信息选择路由。相关研究包括：GEAR(Geographical and Energy Aware Routing)机制[5]、GEM(Graph Embedding)路由[6]和边界定位地理路由[7]等。还有些应用对数据传输的可靠性有较高要求，因此可靠路由协议是路由协议研究的一个重要方向。例如基于不相交路径的多路径路由机制，在这种机制中由于各个路径被设置成不同的优先级，当主路径失效时，次优路径将成为新的主路径。
1.2 无线网络的通信资源分配算法
由于无线通信设备的信道有限，并且信息传播存在干扰，通信资源的分配效率对网络的性能影响很大。近年来出现了许多无线通信技术，用于提高无线网络的通信能力。
码分多址接入CDMA(Code Division Multiple Access)是在扩频通信技术上发展起来的一种崭新而成熟的无线通信技术。CDMA技术的原理是基于扩频技术，即将需传送的具有一定信号带宽信息数据，用一个带宽远大于信号带宽的高速伪随机码进行调制，使原数据信号的带宽被扩展，再经载波调制并发送出去。接收端使用完全相同的伪随机码，与接收的带宽信号作相关处理，把宽带信号换成原信息数据的窄带信号即解扩，以实现信息通信。
时分多址接入TDMA(Time Division Multiple Access)是把一个传输通道进行时间分割以传送若干话路的信息，把N个话路设备接到一条公共的通道上，按一定的次序轮流地给各个设备分配一段使用通道的时间。当轮到某个设备时，这个设备与通道接通，执行操作。与此同时，其他设备与通道的联系均被切断。待指定的使用时间间隔一到，则通过时分多路转换开关把通道连接到下一个要连接的设备上去。
频分多址接入FDMA(Frequency Division Multiple Access)是数据通信中的一种技术，即不同的用户分配在时隙相同而频率不同的信道上。按照这种技术，把在频分多路传输系统中集中控制的频段根据要求分配给用户。同固定分配系统相比，频分多址使通道容量可根据要求动态地进行交换。
2 基于工业无线网络的路由协议
2.1 家族谱系描述方法
家族谱系也称“家谱”，是一种记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。世系图是家谱的一个重要组成部分。家谱在立谱时，便确定了家族世系命名的辈分序列，而且事先标定字号、辈分。本文从网络拓扑角度出发，借用家谱的术语和结构关系进行网络结构和路由协议的描述。
图1所示为典型的树型结构网络拓扑。树型结构是一类重要的非线性数据结构。该结构中，有且仅有一个根(Root)，如A节点。互补相交的有限集均称为子树。节点的子树的根称为该节点的孩子(Child)，该节点相应地称为孩子的双亲(Parent)。同一个双亲的孩子之间互称为兄弟(Sibling)。没有孩子的节点的节点也被称为叶子(Leaf)。这是数据结构中对树的定义。

本文根据家族谱系中的称谓和关系，将其对应到树型结构中的节点和节点之间的关系。使得对网络拓扑和路由协议的描述更加清晰、方便、易于理解。
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所示。