提出了一种基于ZlgBee无线自组网络用于自动化质监的电子秤路由算法。以DGT-CC为蓝本，使用更加完善的 局部流量均衡策略来规避拥塞，并为无线自组网构建流量均衡的数据汇集树路由。通过本路由算法可以高效、快速地收 集电子秤数据信息，实现高效方便的质监。
引言
本文提出了一种用于自动化质监的电子秤无线自组 网的路由算法，通过为电子秤嵌入质监模块来自动收集电 子秤示数的信息，质监模块之间采用ZgBee组建无线自 组网进行数据的汇集与共享，而自组网建立后可以通过 WiFi将数据发送至智能手机终端，从而方便监测电子秤 示数是否与电磁砝码重量相符，即是否存在质量问题。
1.电子秤无线自组网
1.1电子秤无线自组网模型定义
电子秤无线自组网以电子秤为通信节点，建立无线局 域网来收集由电磁砝码产生的示数，当质监完成后，各个 节点将数据发送至数据汇集节点。电子秤无线自组网网 络模型定义如下：
①电子秤无线自组网各节点随机分布在二维平面内 (三维情况暂不予考虑），且节点位置固定，软硬件条件相 同，所有电子秤节点构成一个自组网集合，记作V，任意可 以直接通信的两个节点构成一个节点对，这个节点对称为 电子秤无线自组网中的一条直接通信边，所有直接通信边的集合记作E。因此，整个电子秤无线自组网可表示成G= (V，E)。
②电子秤无线自组网中节点用N表示，为节点下 标，对于V^eV’N内存容量为M,有限的内存容量决定 了凡能够存储的邻居节点数目有限。
③每个节点凡都有唯一的编号，节点凡的编号记 作addr(0，为0?9 999之间的整数，可以参与排序，是节 点参与ZgBe e组网时协调器分配的网络地址。
④对于V^eV，如果3 eiGE (i是直接通信边），且 ei的一个端点是N，那么a的另一端点称为节点凡的邻 居节点，节点凡所有邻居节点的总个数称作节点凡的 度，记作d(N,)。
⑤电子秤无线自组网存在一个数据汇集节点N-， 自组网中所有节点都将数据传输给汇集节点Nsl?k，节点 N,到节点Nsl?k经历的最短路径（最小跳数）记为h(N,)， (凡）表示节点N的邻居节点N到数据汇集节点Nsl?k 的最短路径。
⑥节点凡的所有邻居节点组成一个邻居节点集合，记作L(N,)。
⑦设定每个电子秤无线自组网节点都发送而且只发送一次数据给数据汇集节点Nsink，从第一个节点开始发送 数据起，到所有节点数据发送完毕的这段时间称为电子秤 无线自组网的一个数据发送周期，记作丁。
⑧电子秤无线自组网中的节点依附于电子秤设备， 所以一般认为N;能量无限（V)，并且在数据收集 的这段时间内，节点N是固定的，节点凡的接收和发送 队列容量有限，即如果一段时间内有多个节点向N;发送 数据包，数据包会有一定的丢失概率，将节点N;数据处理 能力（即单位时间接收和发送数据的速度）记为B。
⑨到数据汇集节点N-的最短路径相同的节点的集 合称为同层节点，“层”用来衡量节点到数据汇集节点N- 的最短路径的长度，VNi€ V，如果h(N; = k)，那么称N; 为第k层节点，同理，k层节点就是指所有到数据汇集节 点N-的最短路径为k的节点的集合。
⑩如果h(N) = h(Ni) — l，那么N就 是凡的一个候选父节点，N;的所有候选父节点组成的集 合记作F(Ni)，组网时N会按照流量均衡的原则选择 F(N)中的某个节点作为自己的父节点。如果N;选择N 作为父节点，那么N被称为N的子节点，任意节点（除 N-)的父节点有且只有一个。
1.2电子秤无线自组网模型性能分析
时延和能耗是反映无线自组网性能的重要指标，在本 系统中，各节点直接安装在电子秤内，节点能量依附于电 子秤，因此可以认为无线自组网各节点能量是无限的，所 以采用节点总操作数来衡量节点及网络寿命。节点总操 作数指一个数据发送周期丁内，节点N执行的所有操作 (包括接收数据包、发送数据包、解析指令、查找路由、数据 聚合等），所有操作总数称为节点N;的总操作数，记作 OPCNi)。
假设每次发送数据的大小为K，忽略数据在节点直接 传输的时间，将N;发出的数据包到达数据汇集节点N- 所用的时间作为节点N;至N-的时延，记作D(ND，如下 所示：
D(N;) = Tr(Ni)+Ts(Ni)+Tt(Ni) (N, G V)
其中，丁 XND是节点N;路由发现，即寻找下一跳地址 所用的时间JJN)是节点发送时延，与数据包大小和节 点单位时间发送和接收数据能力相关，丁s(ND的计算如下 所示：
Ts(N;) = K (n, G V)
丁t(N0是数据包从节点N;出发后途经若干中间节点 发送到汇集节点所用的时延，丁t(ND的计算如下所示： Tt(N;) = 2 X h(N;) X Ts(Nt) (N; G V)
如果忽略掉节点因为通信链路忙碌和目的节点忙碌 而等待的时间，假设一个节点只发送一次数据包，在一个 数据发送周期丁内，整个电子秤无线自组网络的全部时 延Dtotal如下所示：
Dtotal = 2 {Tr(Ni)+Ts(Ni)+Tt(Ni)} i=l
VN G V，< i< n 将数据传送至数据汇集节点所经历的最小跳数为 h(Ni)，因此整个电子秤无线自组网的所有节点数据汇集 路径就是数据汇集路径之和，简称路径和，记作H totai，因 此Htotai和Dtotai如下所示：
Htotal = ^h(N)，VN; G V，
i=l
Dtotai = {Tr(N;) +-B }+iKx Htotai X 2
VN; G V，l < i< n 由此发现，网络总时延与路径和存在正相关，网络总 操作数也随着路径和的增加而增加，因此可以得出结论： 网络性能与路径和H totai存在正相关，可以通过降低网络 路径和来提高网络性能。
2 .DGT-CC算法的实现与改进
通过基于拥塞控制的无线传感网络数据汇集树生成 算法 DG丁-CC (Data Gather Tree based on Congestion Control)构建路由树，将与终端智能手机连接的节点设为 Nsink，以N-为根建立一个最短数据路径汇集树，即每个 节点到数据汇集节点的路径都是最短的。设定凡到N- 的跳数为k，那么N;总是从集合L中选择父节点，L是所 有到N-的跳数为（k 一 1)的节点组成的集合，所以凡发 送数据至数据汇集节点N-的下一跳地址就是N;的父 节点。
2.1流量均衡原理
根据流量均衡原理，DG丁-CC算法平衡最短路径数据 汇集树中每一层节点间的流量之差，使得整个网络性能达 到最优。
流量定义：在无线网络中某个节点的流量指一段时间 中该节点发送或者转发的数据包的总大小，电子秤无线自 组网中节点凡（凡€ V)的流量定义为在一个数据发送周 期丁内，N发送或转发的数据包的总大小。由于在电子 秤无线自组网中，各个节点向数据节点发送一次数据，在 每个节点发送数据量相同的情况下，t ( N;)可以简化为以 N,为根的子树的节点数量总和。
流量热点简介：如果大量节点同时向某个特定的节点 发送数据包，那么这个节点就可以称为流量热点。因此， 越靠近N -，流量热点越多，流量热点缓存满了之后，后续 发送过来的数据包会被丢弃，这样势必会导致节点重复发 送数据包，增大网络时延。所以应当平衡热点的流量，防止部分热点流量过大，影响网络性能。
流量均衡原理：对于一棵数据汇集树，假设其深度为
H，观察这棵数据汇集树的第k层（k
…，Nkn，它们的流量分别为)，t(Nk2 )，t (Nk3 )，???， t(N、），在每个节点都发送并只发送一次数据包的前提下，
有 t(Nk1 )+t(Nk2 ) + t(Nk3 )十…+ t(Nkn ) = M，为了达到流 量均衡，即让()，t(Nk2 )，t(Nk )，…，t(Nkn )之间的差值
最小，根据乘法原理，需要确保nt(N)，（1 < i < n)最大。
2.2改进后的局部流量均衡策略
DGT-CC算法中的流量均衡步骤直接来源于流量均 衡原理，对于某个节点，总是选择候选父节点中流量最小 的作为父节点，这样会导致单个节点的流量均衡，有待优 化，因此对局部流量均衡策略进行了改进。
局部流量均衡：一棵数据汇集树的第k层节点的集合 记作 S(k)，N，Nk2，Nk3，…，Nkn e S(k)，如果 t(Nk1 ) x t(Nk2 )X t(Nk3 ) X…X t(N、)取得条件最大值，对于 V t(Nk, ),t(Nk)G S(k)，当 t(%)十 t(Nk;)不变时，必定有 t(Nk, )Xt(Nk)取得最大值。
因此对DGT-CC算法进行改进：对节点x进行流量 均衡调整时，如果节点x的父节点为u，存在v€F(x)，则 有 Max= (t(u) - t(x) ) X (t(v)—t(x))，使 Max〉t(u) X t(v)，那么x将父节点重置为v。
2.3完善后的DGT-CC算法实现
完善后的DGT-CC算法步骤如下：
①所有节点初始化，对于节点Nt，设置d(Nt) =0， L(Nt) = / ,h(Nt) ,F(Nt) = /，（Nt) = 1。
②数据汇集节点发出层次发现广播命令，该命令包 含节点层次计数，记作h(e)，节点N收到该命令后，比较 h(re) + 1和h(Nt)的大小，如果Mre’ + KhCND，则令 ^凡）=从代）十1，然后将命令中的h(re)重置为h(Nt)、 地址重置为addr(i)，并广播该命令，否则丢弃该命令，因 此，所有节点可以得知节点的层次信息。
③所有节点向周围广播发送hello消息，消息包含节 点层次计数，收到的节点缓冲区中没有源节点的信息，则 将源节点的层次和地址信息存入到缓冲区，并且将d(Nt) 自加1。当接收完所有hello消息后，丢弃层次计数大于 h(N)的节点数据，其余的节点数据存入L(Nt)，将L(Nt) 中节点层次计数比h(Nt)小1的节点存入F(Ni)，并向 L(NJ中的所有节点发送包含d(NJ的消息，使每个节点 都能得到邻居节点的度。
④如果节点凡，!1(凡）=1，则N是数据汇集节点 Nsmk
的邻居节点，则N可直接发送请求与N-建立父子 关系；否则，对F(NJ按照节点度从小到大排序，节点度 小的优先被选择，节点度相同时地址小的优先被选择，向 该节点发送请求，得到应答后建立父子关系，通过这一过 程所有节点共同组成一棵最短路径汇集树。
⑤最短路径汇集树生成后，便进行流量统计，每个节 点获取流量信息，数据汇集节点N-广播流量测试命令 flow_test_packet，节点Nt收到该命令后会向父节点发送 流量测试数据包data_Lest，具体步骤略——编者注。
经过一个周期T，每个节点都知道了自身的流量值， 并且通过广播消息发送给所有邻居节点。
⑥改进的流量均衡算法步骤略 编者注，可以避 免流量热点问题，使网络性能达到优化。
2.4路由算法过程举例
选取若干ZigBee全功能节点、节点位置及邻居信息， 随机选取任意一个节点作为ZgBee协调器构建网络，如 图1所示，图中虚线连接表示节点间的邻居关系.图1节点邻居关系及地址编号图
根据网络拓扑图进行流量均衡的数据汇集树生成，经 过算法步骤的①、②、③，所有节点都得了自身的层次h和 节点度d，节点用addr(h，d)的方式表示节点信息，如图2 所示。
根据步骤④来构建最短路径数据汇集，以7号节点为 例，在网络拓扑图中有两个候选父节点，分别是2(1，5)和 3(1，5)，根据条件，当父节点度数相同时选择地址小的父 节点，即2号节点，用带箭头的实线表示子节点向父节点 数据汇集的路径，如图3所示。同时统计该节点的自身流 量信息，在_轮数据汇集周期了后，所有节点都可以得到 自己的流量信息.
从图3中可以看出，号节点的流量明显多于同层节 点，因此需要对以2号为根的子树进行调整，即从叶子节 点开始寻找是否有候选父节点，可见15号节点有调整的 可能，号和8号节点的流量之积为1X4 = 4，调整后为
(1 + 1) X (4一1)=6>4，因此可以进行调整，将7号节点 作为15号节点的父节点，同时更新7号节点流量信息。 对于7号节点，号节点和3号节点的流量之积为10X1 = 10，调整后为（10 — 1)X (1十1) = 18>10，因此将3号节 点作为7号节点的父节点，对于14号节点，由于15号节 点的父节点变为了 7号节点，号节点的流量为3，号节 点和7号节点流量之积为4X3 = 12，若调整14号节点之 后，流星积为（4一2) X (3十2) = 10，因此不需要调整14号 节点。该方法使同层节点流量更加均衡，减少出现部分节 点流量过高影响网络整体性能的情况。调整后的数据汇 集树如图4所示.
3.仿真实验
仿真实验采用OPNET实验平台，使用ZigBee节点 组织无线自组网，选取任意一个节点作为数据汇集节点， 其他节点将数据信息发送到数据汇集节点，仿真网络时延 以及网络中的流量通过设置数据包、节点类型、网络拓扑 结构，呈现仿真结果。将一个数据汇集节点Smk和若干 个普通节点随机均匀分布在区域内，网络结构略——编者 注，算法的仿真结果略 编者注。
4.结语
本文提出了一种基于自动化质监的电子秤无线自组 网路由算法，将电子秤嵌入质监模块，质监人员通过带有 WFi的手机就可以实现电子秤称重示数的收集与检验， 而本路由算法可以帮助质监人员高效地进行检查，防止局 部流量过大导致网络性能受到影响。
