用于自动化质监的电子秤无线自组网路由算法设计※

张韦霆，马维华，王赞森

(南京航空航天大学 计算机科学与技术学院，南京 210016)



用于自动化质监的电子秤无线自组网路由算法设计※

张韦霆，马维华，王赞森

(南京航空航天大学 计算机科学与技术学院，南京 210016)

摘要:提出了一种基于ZigBee无线自组网络用于自动化质监的电子秤路由算法。以DGT-CC为蓝本，使用更加完善的局部流量均衡策略来规避拥塞，并为无线自组网构建流量均衡的数据汇集树路由。通过本路由算法可以高效、快速地收集电子秤数据信息，实现高效方便的质监。

关键词:自动化质监；无线自组网；DGT-CC算法；路由

引言

本文提出了一种用于自动化质监的电子秤无线自组网的路由算法，通过为电子秤嵌入质监模块来自动收集电子秤示数的信息，质监模块之间采用ZigBee组建无线自组网进行数据的汇集与共享，而自组网建立后可以通过WiFi将数据发送至智能手机终端，从而方便监测电子秤示数是否与电磁砝码重量相符，即是否存在质量问题。

1电子秤无线自组网

1.1电子秤无线自组网模型定义

电子秤无线自组网以电子秤为通信节点，建立无线局域网来收集由电磁砝码产生的示数，当质监完成后，各个节点将数据发送至数据汇集节点。电子秤无线自组网网络模型定义如下：

① 电子秤无线自组网各节点随机分布在二维平面内(三维情况暂不予考虑)，且节点位置固定，软硬件条件相同，所有电子秤节点构成一个自组网集合，记作V，任意可以直接通信的两个节点构成一个节点对，这个节点对称为电子秤无线自组网中的一条直接通信边，所有直接通信边的集合记作E。因此，整个电子秤无线自组网可表示成G=(V,E)。

② 电子秤无线自组网中节点用N表示，i为节点下标，对于∀Ni∈V，N内存容量为M，有限的内存容量决定了Ni能够存储的邻居节点数目有限。

③ 每个节点Ni都有唯一的编号，节点Ni的编号记作addr(i)，为0～9 999之间的整数，可以参与排序，是节点参与ZigBee组网时协调器分配的网络地址。

④ 对于∀Ni∈V，如果∃ei∈E (ei是直接通信边)，且ei的一个端点是Ni，那么ei的另一端点称为节点Ni的邻居节点，节点Ni所有邻居节点的总个数称作节点Ni的度，记作d(Ni)。

⑤ 电子秤无线自组网存在一个数据汇集节点Nsink，自组网中所有节点都将数据传输给汇集节点Nsink，节点Ni到节点Nsink经历的最短路径(最小跳数)记为h(Ni)，hNi(Nj)表示节点Ni的邻居节点Ni到数据汇集节点Nsink的最短路径。

⑥ 节点Ni的所有邻居节点组成一个邻居节点集合，记作L(Ni)。

⑦ 设定每个电子秤无线自组网节点都发送而且只发送一次数据给数据汇集节点Nsink，从第一个节点开始发送数据起，到所有节点数据发送完毕的这段时间称为电子秤无线自组网的一个数据发送周期，记作T。

⑧ 电子秤无线自组网中的节点依附于电子秤设备，所以一般认为Ni能量无限(∀Ni∈V)，并且在数据收集的这段时间内，节点Ni是固定的，节点Ni的接收和发送队列容量有限，即如果一段时间内有多个节点向Ni发送数据包，数据包会有一定的丢失概率，将节点Ni数据处理能力(即单位时间接收和发送数据的速度)记为B。

⑨ 到数据汇集节点Nsink的最短路径相同的节点的集合称为同层节点，“层”用来衡量节点到数据汇集节点Nsink的最短路径的长度，∀Ni∈V，如果h(Ni=k)，那么称Ni为第k层节点，同理，k层节点就是指所有到数据汇集节点Nsink的最短路径为k的节点的集合。

⑩ 如果Nj∈L(Ni)且h(Nj)=h(Ni)-1，那么Nj就是Ni的一个候选父节点，Ni的所有候选父节点组成的集合记作F(Ni)，组网时Ni会按照流量均衡的原则选择F(Ni)中的某个节点作为自己的父节点。如果Ni选择Nj作为父节点，那么Ni被称为Nj的子节点，任意节点(除Nsink)的父节点有且只有一个。

1.2电子秤无线自组网模型性能分析

时延和能耗是反映无线自组网性能的重要指标，在本系统中，各节点直接安装在电子秤内，节点能量依附于电子秤，因此可以认为无线自组网各节点能量是无限的，所以采用节点总操作数来衡量节点及网络寿命。节点总操作数指一个数据发送周期T内，节点Ni执行的所有操作(包括接收数据包、发送数据包、解析指令、查找路由、数据聚合等)，所有操作总数称为节点Ni的总操作数，记作OP(Ni)。

假设每次发送数据的大小为K，忽略数据在节点直接传输的时间，将Ni发出的数据包到达数据汇集节点Nsink所用的时间作为节点Ni至Nsink的时延，记作D(Ni)，如下所示：

其中，Tr(Ni)是节点Ni路由发现，即寻找下一跳地址所用的时间；Ts(Ni)是节点发送时延，与数据包大小和节点单位时间发送和接收数据能力相关，Ts(Ni)的计算如下所示：

Tt(Ni)是数据包从节点Ni出发后途经若干中间节点发送到汇集节点所用的时延，Tt(Ni)的计算如下所示：

如果忽略掉节点因为通信链路忙碌和目的节点忙碌而等待的时间，假设一个节点只发送一次数据包，在一个数据发送周期T内，整个电子秤无线自组网络的全部时延Dtotal如下所示：

∀Ni∈V,1≤i≤n

将数据传送至数据汇集节点所经历的最小跳数为h(Ni)，因此整个电子秤无线自组网的所有节点数据汇集路径就是数据汇集路径之和，简称路径和，记作Htotal，因此Htotal和Dtotal如下所示：

∀Ni∈V,1≤i≤n

由此发现,网络总时延与路径和存在正相关，网络总操作数也随着路径和的增加而增加，因此可以得出结论:网络性能与路径和Htotal存在正相关，可以通过降低网络路径和来提高网络性能。

2DGT-CC算法的实现与改进

通过基于拥塞控制的无线传感网络数据汇集树生成算法DGT-CC (Data Gather Tree based on Congestion Control)构建路由树，将与终端智能手机连接的节点设为Nsink，以Nsink为根建立一个最短数据路径汇集树，即每个节点到数据汇集节点的路径都是最短的。设定Ni到Nsink的跳数为k，那么Ni总是从集合L中选择父节点，L是所有到Nsink的跳数为(k-1)的节点组成的集合，所以Ni发送数据至数据汇集节点Nsink的下一跳地址就是Ni的父节点。

2.1流量均衡原理

根据流量均衡原理，DGT-CC算法平衡最短路径数据汇集树中每一层节点间的流量之差，使得整个网络性能达到最优。

流量定义：在无线网络中某个节点的流量指一段时间中该节点发送或者转发的数据包的总大小，电子秤无线自组网中节点Ni(Ni∈V)的流量定义为在一个数据发送周期T内，Ni发送或转发的数据包的总大小。由于在电子秤无线自组网中，各个节点向数据节点发送一次数据，在每个节点发送数据量相同的情况下，t(Ni)可以简化为以Ni为根的子树的节点数量总和。

流量热点简介：如果大量节点同时向某个特定的节点发送数据包，那么这个节点就可以称为流量热点。因此，越靠近Nsink，流量热点越多，流量热点缓存满了之后，后续发送过来的数据包会被丢弃，这样势必会导致节点重复发送数据包，增大网络时延。所以应当平衡热点的流量，防止部分热点流量过大，影响网络性能。

2.2改进后的局部流量均衡策略

DGT-CC算法中的流量均衡步骤直接来源于流量均衡原理，对于某个节点，总是选择候选父节点中流量最小的作为父节点,这样会导致单个节点的流量均衡，有待优化，因此对局部流量均衡策略进行了改进。

局部流量均衡：一棵数据汇集树的第k层节点的集合记作S(k),Nk1,Nk2,Nk3,…,Nkn∈S(k)，如果t(Nk1)×t(Nk2)×t(Nk3)×…×t(Nkn)取得条件最大值，对于∀t(Nki),t(Nkj)∈S(k)，当t(Nki)+t(Nkj)不变时，必定有t(Nki)×t(Nkj)取得最大值。

因此对DGT-CC算法进行改进：对节点x进行流量均衡调整时，如果节点x的父节点为u，存在v∈F(x)，则有Max=(t(u)-t(x))×(t(v)-t(x))，使Max>t(u)×t(v)，那么x将父节点重置为v。

2.3完善后的DGT-CC算法实现

完善后的DGT-CC算法步骤如下：

①所有节点初始化，对于节点Ni，设置d(Ni)=0，L(Ni)=∅，h(Ni)=∞，F(Ni)=∅，t(Ni)=1。

② 数据汇集节点发出层次发现广播命令，该命令包含节点层次计数，记作h(re)，节点Ni收到该命令后，比较h(re)+1和h(Ni)的大小，如果h(re)+1

③ 所有节点向周围广播发送hello消息，消息包含节点层次计数，收到的节点缓冲区中没有源节点的信息，则将源节点的层次和地址信息存入到缓冲区，并且将d(Ni)自加1。当接收完所有hello消息后，丢弃层次计数大于h(Ni)的节点数据，其余的节点数据存入L(Ni)，将L(Ni)中节点层次计数比h(Ni)小1的节点存入F(Ni)，并向L(Ni)中的所有节点发送包含d(Ni)的消息，使每个节点都能得到邻居节点的度。

④ 如果节点Ni，h(Ni)=1，则Ni是数据汇集节点Nsink的邻居节点，则Ni可直接发送请求与Nsink建立父子关系；否则，Ni对F(Ni)按照节点度从小到大排序，节点度小的优先被选择，节点度相同时地址小的优先被选择，向该节点发送请求，得到应答后建立父子关系，通过这一过程所有节点共同组成一棵最短路径汇集树。

⑤ 最短路径汇集树生成后，便进行流量统计，每个节点获取流量信息，数据汇集节点Nsink广播流量测试命令flow_test_packet，节点Ni收到该命令后会向父节点发送流量测试数据包data_test，具体步骤略——编者注。

经过一个周期T，每个节点都知道了自身的流量值，并且通过广播消息发送给所有邻居节点。

⑥ 改进的流量均衡算法步骤略——编者注，可以避免流量热点问题，使网络性能达到优化。

2.4路由算法过程举例

选取若干ZigBee全功能节点、节点位置及邻居信息，随机选取任意一个节点作为ZigBee协调器构建网络，如图1所示，图中虚线连接表示节点间的邻居关系。

图1　节点邻居关系及地址编号图

根据网络拓扑图进行流量均衡的数据汇集树生成，经过算法步骤的①、②、③，所有节点都得了自身的层次h和节点度d，节点用addr(h,d)的方式表示节点信息，如图 2所示。

图2　节点层次与节点度示意图

根据步骤④来构建最短路径数据汇集，以7号节点为例，在网络拓扑图中有两个候选父节点，分别是2(1，5)和3(1，5)，根据条件，当父节点度数相同时选择地址小的父节点，即2号节点，用带箭头的实线表示子节点向父节点数据汇集的路径，如图3所示。同时统计该节点的自身流量信息，在一轮数据汇集周期T后，所有节点都可以得到自己的流量信息。

图3　最短路径数据汇集树

从图3中可以看出，2号节点的流量明显多于同层节点，因此需要对以2号为根的子树进行调整，即从叶子节点开始寻找是否有候选父节点，可见15号节点有调整的可能，7号和8号节点的流量之积为1×4=4，调整后为(1+1)×(4-1)=6>4，因此可以进行调整，将7号节点作为15号节点的父节点，同时更新7号节点流量信息。对于7号节点，2号节点和3号节点的流量之积为10×1=10，调整后为(10-1)×(1+1)=18>10，因此将3号节点作为7号节点的父节点，对于14号节点，由于15号节点的父节点变为了7号节点，7号节点的流量为3，6号节点和7号节点流量之积为4×3=12，若调整14号节点之后，流量积为(4-2)×(3+2)=10，因此不需要调整14号节点。该方法使同层节点流量更加均衡，减少出现部分节点流量过高影响网络整体性能的情况。调整后的数据汇集树如图4所示。

图4　调整后的数据汇集树

3仿真实验

仿真实验采用OPNET实验平台，使用ZigBee节点组织无线自组网，选取任意一个节点作为数据汇集节点，其他节点将数据信息发送到数据汇集节点，仿真网络时延以及网络中的流量通过设置数据包、节点类型、网络拓扑结构，呈现仿真结果。将一个数据汇集节点Sink和若干个普通节点随机均匀分布在区域内，网络结构略——编者注，算法的仿真结果略——编者注。

结语

本文提出了一种基于自动化质监的电子秤无线自组网路由算法，将电子秤嵌入质监模块，质监人员通过带有WiFi的手机就可以实现电子秤称重示数的收集与检验，而本路由算法可以帮助质监人员高效地进行检查，防止局部流量过大导致网络性能受到影响。

参考文献

[1] 石为人,唐云建,王燕霞.基于拥塞控制的无线传感器网络数据汇集树生成算法[J] .自动化学报,2010(6).

[2] 王赞森,马维华.手机WiFi热点的电子秤自动质监系统设计[J] .单片机与嵌入式系统应用,2014(4).

[3] 梁平原,陈炳权,谭子尤.无线传感器网络数据采集关键技术及研究进展[J] .吉首大学学报:自然科学版,2011(1).

[4] 费晓飞,胡捍英.无线传感器网邻居发现算法研究[J] .微计算机信息,2009(4).

张韦霆、王赞森(硕士研究生)，马维华(教授)：研究方向为嵌入式系统应用。

Wireless Ad Hoc Networks Routing Algorithm of Electronic Scale for

Automatic Quality Supervision※

Zhang Weiting,Ma Weihua,Wang Zansen

(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

Abstract：A wireless Ad Hoc networks routing algorithm based on ZigBee of electronic scale for automatic quality supervision is proposed.Based on DGT-CC algorithm,a more perfect local traffic equilibrium strategy is used to avoid congestion,and a traffic balanced data collection tree routing is constructed.The electronic scale data information can be collected efficiently and quickly using the routing algorithm,and the quality supervision can be achieved easily.

Key words:automatic quality supervision;Ad Hoc network;DGT-CC algorithm;route

收稿日期：(责任编辑：薛士然2015-07-27)

中图分类号:TP301.6

文献标识码:A