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

沈 威，许 娜

(1.中国科学院研究生院，北京 100049；2.北京控制工程研究所，北京 100190)

在无线传感器网络中，路由协议负责将数据分组从源节点通过网络转发到目的节点。路由的关键是要寻找源节点到目的节点间通信延迟较小的路径，提高整个网络的利用率，避免通信拥塞并均衡网络流量。传感器网络的路由机制经常与数据融合技术一起应用，通过减少通信量来节省能量。WIA-PA工业无线标准规定[2]：设备在加入网络后，各个路由设备通过发送信标帧来分配通信资源。信标帧中含有路由设备自身的超帧结构信息。超帧是一种用来组织网络通信时间分配的逻辑结构。超帧机制要求通信设备之间的时间精确同步，而时间信息的传播依赖于网络的路由。路由的实现离不开网络管理者对通信资源的分配，通信资源的分配效率将直接影响网络各方面的性能。

1相关研究

1.1无线网络的路由协议

随着无线传感器网络技术的发展，出现许多专门针对无线传感器网络的路由协议。根据应用目标的不同，这些路由协议大致可分为四种类型：能量感知路由协议、基于查询的路由协议、地理位置路由协议和可靠路由协议。

能量感知路由主要是根据节点的可用能量(剩余能量)或传输路径上的能量需求，选择数据的转发路径。为了均衡消耗整个网络的能量，SHAH R C.等人提出了一种能量多路径路由机制[3]。其核心思想是在源节点和目的节点之间建立多条路径，根据路径上节点的通信能耗以及节点的剩余能量，给每条路径设置一个被选择的概率，将通信能耗分散到多条路径上，延长网络的寿命。

定向扩散是一种基于查询的以数据为中心的路由机制[4]。汇聚节点根据应用需求，广播兴趣消息启动路由建立过程。中间节点通过兴趣表建立从数据源到汇聚节点的数据传输梯度，自动形成数据传输的多条路径。在这多条路径中，使用路径加强机制生成一条优化的数据传输路径。基于查询的路由协议还有适用于数据传输量较小的传感器网络的谣传路由等。

在某些应用中，节点需要获取它的位置信息，如森林防火。地理位置路由假设节点已知自己的地理位置信息，以及目的节点或目的区域的地理位置，并依据这些地理信息选择路由。相关研究包括：GEAR(Geographical and EnergyAwareRouting)机 制[5]、GEM(Graph Embedding)路由[6]和边界定位地理路由[7]等。还有些应用对数据传输的可靠性有较高要求，因此可靠路由协议是路由协议研究的一个重要方向。例如基于不相交路径的多路径路由机制，在这种机制中由于各个路径被设置成不同的优先级，当主路径失效时，次优路径将成为新的主路径。

1.2无线网络的通信资源分配算法

由于无线通信设备的信道有限，并且信息传播存在干扰，通信资源的分配效率对网络的性能影响很大。近年来出现了许多无线通信技术，用于提高无线网络的通信能力。

码分多址接入CDMA(Code Division Multiple Access)是在扩频通信技术上发展起来的一种崭新而成熟的无线通信技术。CDMA技术的原理是基于扩频技术，即将需传送的具有一定信号带宽信息数据，用一个带宽远大于信号带宽的高速伪随机码进行调制，使原数据信号的带宽被扩展，再经载波调制并发送出去。接收端使用完全相同的伪随机码，与接收的带宽信号作相关处理，把宽带信号换成原信息数据的窄带信号即解扩，以实现信息通信。

在前期预实验的基础上，以综合评价、破碎力、挥发性成分和含油量为指标，分别考察不同切片厚度（1、3、5、7 mm）、漂烫温度（70、80、90、100 ℃）、漂烫时间（1、3、5、7 min）、浸渍液（添加0.1%的食盐浓度和不添加食盐）、冷冻时间（1、2、3、4 h）5个预处理单因素对马铃薯脆片产品品质的影响。经样品预处理后进行真空油炸，真空油炸参数为：真空度0.098 MPa、油炸温度（88±2）℃、时间32 min、离心脱油转速400 r/min、时间6 min。

时分多址接入TDMA(Time Division Multiple Access)是把一个传输通道进行时间分割以传送若干话路的信息，把N个话路设备接到一条公共的通道上，按一定的次序轮流地给各个设备分配一段使用通道的时间。当轮到某个设备时，这个设备与通道接通，执行操作。与此同时，其他设备与通道的联系均被切断。待指定的使用时间间隔一到，则通过时分多路转换开关把通道连接到下一个要连接的设备上去。

频分多址接入FDMA(Frequency Division Multiple Access)是数据通信中的一种技术，即不同的用户分配在时隙相同而频率不同的信道上。按照这种技术，把在频分多路传输系统中集中控制的频段根据要求分配给用户。同固定分配系统相比，频分多址使通道容量可根据要求动态地进行交换。

2基于工业无线网络的路由协议

2.1家族谱系描述方法

家族谱系也称“家谱”，是一种记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。世系图是家谱的一个重要组成部分。家谱在立谱时，便确定了家族世系命名的辈分序列，而且事先标定字号、辈分。本文从网络拓扑角度出发，借用家谱的术语和结构关系进行网络结构和路由协议的描述。

图1所示为典型的树型结构网络拓扑。树型结构是一类重要的非线性数据结构。该结构中，有且仅有一个根(Root)，如A节点。互补相交的有限集均称为子树。节点的子树的根称为该节点的孩子(Child)，该节点相应地称为孩子的双亲(Parent)。同一个双亲的孩子之间互称为兄弟 (Sibling)。没有孩子的节点的节点也被称为叶子(Leaf)。这是数据结构中对树的定义。

图1 典型的树型结构网络拓扑

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

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所示。

图2 数据包的交互过程

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

图3 树型结构线性存储报文格式

3基于工业无线网络的通信资源分配算法

3.1信道与时隙的分配原则

由于无线传感器网络的通信特点，不同设备在相互通信时存在干扰。要想同时通信，相邻层之间不可分配相同的信道。对于信道的分配，可以设置n层作为一个信道重复周期。假设n=3，如图4所示，Root节点与第1代通信使用ch1信道，第1代与第2代通信使用ch2信道，第2代与第3代通信使用ch3信道，第3代与第4代通信可以重复使用ch1信道，如此循环。

图4 信道分配实例

由于无线传感器网络中的节点一般只装备一套射频装置，所以节点之间进行单播通信时需要分时。

父节点可以向所有子节点发送广播报文，例如：时间同步报文、数据查询报文等。如果不同父节点发送的广播报文覆盖范围重合，子节点在接收时就存在干扰，需要分时。如图4所示，节点1的广播范围覆盖节点4、5，节点2的广播范围覆盖节点6，则节点5和节点 6不能同时接收父节点发送的广播报文。在家族树结构中，需要分时通信的情况还包括：父节点相同的节点在与其父节点通信时，需要分时；存在干扰的堂兄弟节点在与其父节点通信时，需要分时。

3.2通信资源的分配算法

网络可用图 G=(V，E)来表示，网络节点数 n=|V|，对e∈E，定义代价函数 Cost(e)：E→R+，时延函数 Delay(e)：E→R+。节点i加入网络时，先通过父节点从网络管理者处获取 ID信息，启动 Cal_Tree()过程，进行路由选择和通信资源分配。伪代码如下：

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

4仿真实验及分析

仿真实验在OMNet++平台上进行，拓扑采用8×8的Mesh结构，64个节点中包含一个网络管理者，负责全网络通信资源的分配。实验节点以中科院自主设计的GAINS-2节点为原型，该节点与Mica2节点兼容。节点的微控制器采用Atmega128L，射频芯片采用CC1000。网络协议用Visual C++开发，网络拓扑由.ned文件生成。

在网络正常监控阶段，当用户端有查询任务时，查询报文将沿着网络的拓扑结构传播。图6为模拟系统随机生成的网络拓扑以及路由协议建立的树型结构。查询任务一般具有周期性，沿网络的梯度方向传播。

网络维护代价、平均加入时延和平均传输时延是衡量路由协议和通信资源分配算法性能的一个重要指标。仿真实验结果如图7所示，数据的传输时延与链路的质量密切相关。

在仿真实验中，保持监控区域面积不变，改变网络中节点的数目，为达到应用要求，需要增加节点的射频距离，则能耗代价与节点的数目密切相关。图8为网络能耗代价与节点数目之间的变化关系。

工业无线传感器监测网络技术是无线网络研究领域的一个新的研究方向。本文采用家族谱系的描述方法，提出了一种适用于复杂工业现场监测的工业无线传感器网络的路由和通信资源分配算法。这种通信资源分配算法采用分层、分时、分频相结合的通信策略，充分利用了无线传感器网络的特性，能够有效提高无线网络的通信效率。由于工业无线监测网络的工作环境具有多样性，因此，未来的一个重要任务就是提高路由和通信资源分配算法的适应性和可靠性，克服外界环境变化造成的影响。

[1]孙利民，李建中，陈渝.无线传感器网络[M].北京：清华大学出版社，2005.

[2]Industrial communication networks-fieldbus specifications-WIA-PA communication network and communication profile[EB/OL].http：//www.iec.ch，IEC/PAS65C/518/RVD.2010.

[3]SHAH R C， RABAEY J M．Energy aware routing for low energy ad hoc sensor networks[C]．IEEE Wireless Communications and Networking Conference， IEEE， 2002(3)：17-21．

[4]IITANAGONWIWAT C， GOVINDAN R， ESTRIN D.Directed diffusion：A scalable and robustcommunication paradigm for sensor networks[C].The 6th Annual InternationalConference on Mobile Computing and Networks，Boston， MA.2000(5)：113-120.

[5]YU Y，GOVINDAN R，ESTRIN D.Geographical and energy aware routing：A recursive data dissemination protocol for wireless sensor networks[R].UCLA Computer Science DepartmentTechnicalReportUCLA/CSD-TR-01-0023.2001(5)：1132-1145.

[6]KARP B， KUNG H T.GPSR：Greedy perimeter stateless routing for wireless networks[C].The 6th Annual InternationalConference on Mobile Computing and Networks，Boston， MA.2000(5)：6-11.

[7]RAO A， RATNASAMY S， PAPADIMITRIOU C.Geographic routing without location information[C].The 9th Annual InternationalConferenceon MobileComputingand Networks， San Diego， CA.2003(9)：96-108．