本文作者(林秀萍,黄旭明),请您在阅读本文时尊重作者版权。
基于蚁群算法和令牌机制的电力线载波自动抄表系统路由算法(2)
第三层及以后的组网方法：
可以参考第二层组网方法，直到集中器搜索到全部节点且路由表记录n个节点逻辑地址和路由信息，初始化组网结束，其形成的逻辑拓扑结构如图2。
因此，在初始化组网后可以得到以下结论：设集中器记录形成一级网络节点个数为y1（1≤y1≤n），二级子网的网络节点个数为y2，并且 y2j=y2；通过二级网络连接的三级网络节点个数为y3，……，当所有的节点都组网成功后，有yi=n,k=1,2,3,…。
2.2 具体组网算例
设某相系统由1个集中器和16个节点组成。利用蚁群算法自组网络后，可以构成如图2所示的结构。集中器发送探索数据包分别被5，6，7，8等4个节点监听到，四个节点向集中器发送应答数据包，集中器接收应答数据包，在路由表中记录它们的相关信息分配相应的逻辑地址并且定义4个节点的网络层次为1；第二步，集中器发送组网信息给一级子网中的节点，各节点转发信息给剩余的11个节点，其中5联系到15，5记录15的相关信息，并将结果转发集中器，集中器分配15相应的逻辑地址并在路由表中记录路径信息。通过一级子网中4个节点的信息转发，分别联系到15，16，17，18等4个节点，集中器定义这些节点的网络层次为2，第二层子网产生；重复上面步骤，搜索第三层网络中的节点，……，直到集中器对16个节点都搜索完毕，初始化组网结束。 集中器和每一个节点都存储相关的路由链表，记录该节点所管辖的所有节点的物理地址和逻辑地址以及网络层次，路由表的长度和复杂度由网络节点个数和网络层次数目决定。图3表示为在经过蚁群算法实现自动网络后形成的三相电力线通信网络逻辑拓扑结构。
2.3 蚁群算法在自组网络中出现的问题
1）由于电力线载波是使用扩频通信的调制方式，通信时载波频率相同，因此线路上只能有一组节点在通信，如果不加以改进直接使用蚁群算法会产生载波冲突问题[12]；（2）节点上的CPU运算能力有限，不易使用CSMA/CD等技术在节点上解决载波冲突问题[13-14]，因此引入令牌机制。
3 引入令牌机制的改进蚁群算法
3.1 令牌机制
令牌法（Token Passing）又称许可证法，它利用单向令牌作为介质访问控制的方法。在低压配电网中通过一个单向令牌帧作为网络传送数据的“令牌”（许可证），如果网络中某一节点要发送信息包，该节点只有获得令牌才能传输数据。
3.2 改进算法
3.2.1 组网的初始阶段
组网的初始阶段，集中器向n个节点发送探索数据包，设k个节点（1≤k≤n）收到探索数据包后这些节点将网络信号强度和物理地址等相关信息返回给集中器，集中器按照应答数据包到达的先后顺序和信号强度分配相应的逻辑地址和优先等级（最先收到信息并且信号强度最强的节点其优先等级最高）。对于剩余的n-k个节点，集中器发令牌给优先等级最高的节点x1，由该节点在规定的时间片内作为中继节点对剩余的n-k继续组网，当时间片结束，集中器收回令牌，并对连接到的节点分配逻辑地址记录其路由信息；然后集中器继续对优先级次之的节点发送令牌，继续组网，直到所有的节点都分配相应的逻辑地址，组网的初始阶段完成。
3.2.2 网络优化算法
第一步：簇头诞生
集中器向一级子网中所有节点发送“竞选簇头”数据包，各节点返回网络信号强度、历史抄送概率等相关信息给集中器，集中器比较这些信息，若某一节点信息值大于规定的阈值，就将该节点定义为簇头，否则释放该一级子网节点，并在接下来的时间段内选择加入某一个簇。设集中器在n个节点的网络中定义了t个簇头（1≤t≤n,t≤k），记录这些簇头的相关信息及优先等级并且发送“竞选成功”信息包给t个簇头，获得簇头标志的节点具备组网的权利。
第二步：簇的形成
集中器发令牌给优先等级最高的簇头节点x1，在规定的时间片内，该簇头获得组网的权利 ，它发送“重新加入簇”数据包告知其下所有节点，非簇头节点根据与簇头的网络信息强度决定是否加入或放弃该簇头，若信息值大于某个阈值，则加入该簇头，否则放弃而投入其他簇头。设在剩余n-t个节点中有y个节点（1≤y≤n-t）响应x1，x1根据接收到的节点的先后顺序将应答信息顺序返回集中器，集中器记录x1下所有可以连接到的节点，分配相应的逻辑地址并刷新路由表，当时间片结束后，集中器收回令牌，第一个簇产生。对于其它的簇头，其组网方法与簇头X1的方法一样。当所有簇头组网结束后，集中器检查所有节点是否都入网。……，继续该步骤，优化网络，保证所有节点入网并且数据都能成功抄送。图4表示经过竞选后产生的分簇网络模型。
