一种基于ISA100.11a标准的一致性组网方法，包括：忽略所有无线设备的功能差别，通过系统管理器收集统计整个网格状网络拓扑的单跳无线通信质量作为其拓扑中点对点之间的权重；评估权重，生成非连通复杂网络拓扑图；使骨干路由器和所有无线设备的非连通复杂网络拓扑图组成全连通的新图；将所有添加的从骨干路由器出发的边的权重记为1；再以骨干路由器节点为根节点，求得其最小生成树；取最小生成树根节点的出度，设为K，则非连通复杂网络拓扑图所含树的最少个数与K值相等，在最小生成树中取得直接与根节点相连的全部节点，将这些节点作为路由设备的节点，实现一致性组网。本发明能以最少的路由器数量实现整个无线传感器网络的连通。
1.一种基于ISA100.11a标准的一致性组网方法，其特征在于，包括以下步骤：
步骤1，忽略所有无线设备的功能差别，通过系统管理器收集统计整个网格状网络拓扑的单跳无线通信质量作为其拓扑中点对点之间的权重；
步骤2，评估权重，剔除权重值低于通信质量阈值的链接，生成非连通复杂网络拓扑图；
步骤3，令骨干路由器作为根节点并和每个无线设备节点进行连接，使骨干路由器和步骤2生成的所有无线设备的非连通复杂网络拓扑图组成全连通的新图；
步骤4，对步骤3生成的新图，将所有添加的从骨干路由器出发的边的权重记为1；再以骨干路由器节点为根节点，使用朱刘-Edmonds最小生成树算法求得其最小生成树；
具体操作为：首先寻找所有指向除根节点之外其他任意点的最小权重边，形成一个边集合；如果集合中存在环，则将环重构为一个新节点，并对指向新节点的边权重进行更新；
重复进行将环转化为边的操作，直至边集合中不再存在环；最后，在步骤3生成的新图中找到进行过权重更新的边，进而找到这些边指向的点及其环，再在这些环中删除指向该点的环内最小边以打断环，则得到以骨干路由器节点为根节点的最小生成树；
步骤5，对于步骤4所生成的最小生成树，取其根节点的出度，设为K，则步骤2的非连通复杂网络拓扑图所含树的最少个数与K值相等，在最小生成树中取得直接与根节点相连的全部节点，并将这些节点作为路由设备的节点，实现一致性组网。
2.根据权利要求1所述基于ISA100.11a标准的一致性组网方法，其特征在于：所述的步骤2在评估权重时统计每个信道上的双向丢包率，双向丢包率指单跳通路的两个无线设备之间到对方设备的传输丢包率，以此作为网络拓扑有向图的权重。
3.根据权利要求2所述基于ISA100.11a标准的一致性组网方法，其特征在于：所述的步骤2中如果某个单跳通路的两个无线设备之间只有一个方向的权重值高于阈值，也判定这两个设备之间不通，剔除掉这两个设备之间的全部链接。
4.根据权利要求1所述基于ISA100.11a标准的一致性组网方法，其特征在于：所述的步骤3中新图中只有骨干路由器指向所有无线设备的连接是单向连接，其余无线设备之间的连接均是双相连接。
5.根据权利要求1所述基于ISA100.11a标准的一致性组网方法，其特征在于，朱刘-Edmonds最小生成树算法具体数学语言描述如下：1.设有向图G＝(V，E)，其中V是有向图的点集，E是有向图的边集；选择一个点τ∈V作为根节点，对每个边ej∈E设其权重值为ωj；令T＝f(G，τ，W)表示有向图G中以τ为根节点，W＝∑ωj为值的生成树；其中，0＜j＜＝M，M为集合E的个数；2.对于有向图G，遍历除根节点τ之外的所有节点vi∈{V\{τ}}，对每个vi取指向vi的边中权重值最小边，并记录这些边的来源点pi，这些边的集合为P＝{(pi，vi)|vi∈{V\{τ}}；其中，0＜＝i＜N，N为集合V的个数；3.如果P的任意子集不能构成环，则得到最小生成树Tmin＝f(P，τ，W)，其值为W，算法结束；4.如果P中含有可以构成环的子集，则记环为C，并将环C抽象为点vc，并从P中删除C，P←P\C；再在原图的边集E中找到指向环的边e＝(u，v)，e满足 得到环外点u和环内点v；进而在环C中找到指向点v的边e′＝(u′，v)，e′满足u′∈C∧v∈C；将点u指向抽象点vc的边记为ec＝(u，vc)，并将ec添加进P，即P←P\{ec}，ec的权重值ωc＝ω(e)-ω(e′)；如果有多条边作为ec，则只选择ωc最小者加入P；5.重复计算
2和计算4，直至P的任意子集不能构成环；6.考察计算4中的环C，找到P中的边ec在原图中相对应的边e，再在环C中找到和边e＝(u，v)指向相同点v的边e′＝(u′，v)；删除边e′以打断环，将环C中除了边e′以外的边加入P；最后从P中删除ec，将ec在原图中相对应的边e加入P，则得最小生成树Tmin＝f(P，τ，W)，其值为W，算法结束。
6.根据权利要求1所述基于ISA100.11a标准的一致性组网方法，其特征在于：在一个路由设备难以满足树中所有现场设备与之单跳连接时，将需要多跳连接的中继现场设备设置为兼容路由功能的设备，允许其数据链路层转发特定的某个邻居的信息。
一种基于ISA100.11a标准的一致性组网方法
技术领域
[0001] 本发明涉及无线传感器网络设计方法，具体涉及一种基于ISA100.11a标准的一致性组网方法，在保证数据采集和通信的前提下，减少路由设备的数量，实现网络拓扑动态更新。
背景技术
[0002] 目前工业领域最常使用的无线传感器网络标准分别有ISA100.11a、Wireless HART和WIA-PA协议。在这些标准中，都定义了搭载传感器的现场设备和负责无线转发的路由设备，这两类无线设备通过适当的拓扑组网，组成满足一定采集覆盖面要求的无线传感器网络。
[0003] 在网络部署时，考虑到路由设备相比于现场设备往往需要负担更多的无线传输任务，同时为了在保证使用需求的前提下尽量满足无线网络低成本、低能耗的要求，通常会根据工业现场的环境尝试不同的网络拓扑结构，最终调试出在保持一定工业现场设备测点的前提下使用路由设备最少的方案。然而，现场设备和路由设备虽能各司其职，但难以满足实时多变的工业环境下的无线网络动态自组网调整需求，一旦因为某些原因导致部分现场设备无法连接到最近的路由设备时，就会造成这些现场设备退网的情况，从而只能由网络维护人员重新人工修改该部分的无线设备部署方案。上述三种无线协议标准也对该现象提出了一些增加灵活性的修改：ISA100.11a定义了兼容现场设备和路由设备的全功能设备，即通过组态可以自由配置无线设备是否具备采集功能或路由功能；Wireless HART则使无线现场设备都具有路由功能；WIA-PA则从早期的专用路由设备改变为将路由功能作为无线现场设备的一部分。
[0004] 对于兼容现场设备和路由设备这两种角色的无线设备在三大无线协议标准中都得到重视，这对增强网络动态自组网的灵活性带来了设备基础。但是具体如何利用无线设备的角色转换来实现灵活组网并不在协议中规定，传统的最大路径算法又容易造成路由设备过多从而使能够执行传感采集任务的有效现场设备数量过少，降低了网络的整体效率和信息采集能力。
发明内容
[0005] 本发明的目的在于针对上述现有技术中的问题，提供一种基于ISA100.11a标准的一致性组网方法，相关无线设备需要具备在现场设备和路由设备这两种角色之间转换的能力，在保证数据采集和通信的前提下，能够以最少的路由器数量实现整个无线传感器网络的连通。
[0006] 为了实现上述目的，本发明采用的技术方案包括以下步骤：
[0007] 步骤1，忽略所有无线设备的功能差别，通过系统管理器收集统计整个网格状网络拓扑的单跳无线通信质量作为其拓扑中点对点之间的权重；
[0008] 步骤2，评估权重，剔除权重值低于通信质量阈值的链接，生成非连通复杂网络拓扑图；
[0009] 步骤3，令骨干路由器作为根节点并和每个无线设备节点进行连接，使骨干路由器和步骤2生成的所有无线设备的非连通复杂网络拓扑图组成全连通的新图；
[0010] 步骤4，对步骤3生成的新图，将所有添加的从骨干路由器出发的边的权重记为1；再以骨干路由器节点为根节点，使用朱刘-Edmonds最小生成树算法求得其最小生成树；
[0011] 步骤5，对于步骤4所生成的最小生成树，取其根节点的出度，设为K，则步骤2的非连通复杂网络拓扑图所含树的最少个数与K值相等，在最小生成树中取得直接与根节点相连的全部节点，并将这些节点作为路由设备的节点，实现一致性组网。
[0012] 所述的步骤2在评估权重时统计每个信道上的双向丢包率，双向丢包率指单跳通路的两个无线设备之间到对方设备的传输丢包率，以此作为网络拓扑有向图的权重。
[0013] 所述的步骤2中如果某个单跳通路的两个无线设备之间只有一个方向的权重值高于阈值，也判定这两个设备之间不通，剔除掉这两个设备之间的全部链接。
[0014] 所述的步骤3中新图中只有骨干路由器指向所有无线设备的连接是单向连接，其余无线设备之间的连接都是双相连接。
[0015] 步骤4的具体操作为：首先寻找所有指向除根节点之外其他任意点的最小权重边，形成一个边集合；如果集合中存在环，则将环重构为一个新节点，并对指向新节点的边权重进行更新；重复进行将环转化为边的操作，直至边集合中不再存在环；最后，在步骤3生成的新图中找到进行过权重更新的边，进而找到这些边指向的点及其环，再在这些环中删除指向该点的环内最小边以打断环，则得到以骨干路由器节点为根节点的最小生成树。
[0016] 朱刘-Edmonds最小生成树算法具体数学语言描述如下：1.设有向图G＝(V，E)，其中V是有向图的点集，E是有向图的边集；选择一个点τ∈V作为根节点，对每个边ej∈E设其权重值为ωj；令T＝f(G，τ，W)表示有向图G中以τ为根节点，W＝∑ωj为值的生成树；其中，0＜j＜＝M，M为集合E的个数；2.对于有向图G，遍历除根节点τ之外的所有节点vi∈{V\{τ}}，对每个vi取指向vi的边中权重值最小边，并记录这些边的来源点pi，这些边的集合为P＝{(pi，vi)|vi∈{V\{τ}}；其中，0＜＝i＜N，N为集合V的个数；3.如果P的任意子集不能构成环，则得到最小生成树Tmin＝f(P，τ，W)，其值为W，算法结束；4.如果P中含有可以构成环的子集，则记环为C，并将环C抽象为点vc，并从P中删除C，P←P\C；再在原图的边集E中找到指向环的边e＝(u，v)，e满足 得到环外点u和环内点v；进而在环C中找到指向点v的边e′＝(u′，v)，e′满足u′∈C∧v∈C；将点u指向抽象点vc的边记为ec＝(u，vc)，并将ec添加进P，即P←P\{ec}，ec的权重值ωc＝ω(e)-ω(e′)；如果有多条边作为ec，则只选择ωc最小者加入P；5.重复计算2和计算4，直至P的任意子集不能构成环；6.考察计算4中的环C，找到P中的边ec在原图中相对应的边e，再在环C中找到和边e＝(u，v)指向相同点v的边e′＝(u′，v)；删除边e′以打断环，将环C中除了边e′以外的边加入P；最后从P中删除ec，将ec在原图中相对应的边e加入P，则得最小生成树Tmin＝f(P，τ，W)，其值为W，算法结束。
[0017] 在一个路由设备难以满足树中所有现场设备与之单跳连接时，将需要多跳连接的中继现场设备设置为兼容路由功能的设备，允许其数据链路层转发特定的某个邻居的信息。
[0018] 与现有技术相比，本发明具有如下的有益效果：由于路由设备负责大量的无线转发工作，路由设备的数量直接影响到整个无线网络的通信成本，当网络中的无线设备数量一定时，路由设备过多也会挤占现场设备的数量，降低整个无线网络的数据采集量。本发明对任意的非连通拓扑图，能够寻找到其有条件的连通性，这种条件对于ISA100.11a无线网络而言，具体即指保证最少数量的路由设备能够相对的使网络总成本和功耗较低，在组网中同时满足数据采集和通信的需求，还能够减少动态更新网络拓扑时的人工成本。
附图说明
[0019] 图1参考ISA100.11a标准的一般网络部署拓扑图；
[0020] 图2 802.15.4信道分布示意图；
[0021] 图3剔除未达阈值的点对点通信连接的非连通复杂网络拓扑图；
[0022] 图4将骨干路由器作为新节点和所有无线一般设备节点共同构成的连通图；
[0023] 图5选取最小生成树的K个根节点作为路由设备的示意图。
具体实施方式
[0024] 下面结合附图对本发明做进一步的详细说明。
[0025] 首先应明确，本发明所述的组网方法是对于无线设备而言的，即图1中“无线传感网”的范围，在此范围中，所有设备之间皆为无线通信。与传统的最大路径算法不同，本发明所述组网方法的目标是求得最小数量的路由设备。这是因为路由设备负责大量的无线转发工作，因此路由设备的数量直接影响到整个无线网络的通信成本；其次，当网络中的无线设备数量一定时，路由设备过多也会挤占现场设备的数量，降低整个无线网络的数据采集量。
[0026] 所述组网方法具体包括以下步骤：
[0027] 步骤1，将所有无线设备看作是ISA100.11a的一般设备，不考虑其具体为现场设备或路由设备，即忽略其功能差别；系统管理器收集统计整个网格状网络拓扑的单跳无线通信质量作为其拓扑中点对点之间的权重。权重的计算以丢包率为标准，但要考虑到如图2所示的802.15.4信道分布和802.11信道分布的频率重叠干扰，因此总的权重可以由下式得出；
[0028]
[0029] 其中，前一项指802.15.4中的11、12、13、14、16、17、18、19、21、22、23、24频段上的丢包率之和，后一项指802.15.4中的15、20、25频段上的丢包率之和。
[0030] 本步骤的目的是给出表示点对点之间无线通信的通信质量定义，作为后续步骤评估拓扑连通性的根据。对于通信质量的权重计算，参考图2，令802.15.4信道分布和802.11信道分布不重叠的15、20和25号信道为主要的权重贡献者，具体贡献率参考二八原则给出。注意，图2的26号信道在ISA100.11a标准中规定为备用信道，一般不予使用，故不参与权重计算。
[0031] 步骤2，评估权重，并且应该考虑到每个信道上的双向丢包率，即单跳通路的两个无线设备之间应该分别有本设备到对方设备的传输丢包率，以此作为网络拓扑有向图的权重；最后剔除权重值低于通信质量阈值的链接，生成一种非连通复杂网络拓扑图；注意如果某个单跳通路的两个无线设备之间只有一个方向的权重值高于阈值，也认为这两个设备之间不通，需要剔除掉这两个设备之间的全部链接。
[0032] 本步骤的目的是评估无线网络拓扑的连通性，并且在本步骤后不再考虑基于通信质量的拓扑图连接变化，即本步骤生成的拓扑图中任意两点间尚存的边代表其一定是可通的。
[0033] 步骤3，令骨干路由器作为根节点并和每个无线设备节点进行连接，使骨干路由器和步骤2生成的所有无线设备的非连通拓扑图组成全连通的新图；注意不存在从无线设备指向骨干路由器的边，即该连通图中只有骨干路由器指向所有无线设备的单向连接。
[0034] 经过步骤2的操作，整个网络的无线拓扑有可能会成为非连通图，如图3所示。本发明所述一致性组网方法的目的就在于对任意的非连通拓扑图，能够寻找其有条件的连通性，即所谓一致性问题，这种条件对于ISA100.11a无线网络而言，具体指保证最少数量的路由设备可以相对的使网络的总成本和功耗较低。故为了方便求取该条件，需要将非连通图转化为连通图，从而可以将一些连通图算法引入，如图4所示。
[0035] 本发明使用朱刘-Edmonds最小生成树算法来求取无线拓扑的一致性条件。考虑该算法的原因在于，ISA100.11a标准中定义了如图1所示的骨干路由器这一衔接无线传感网和网关的特殊节点，这种网络结构特点使得骨干路由器的存在总能将非连通拓扑衔接为全连通的拓扑，故骨干路由器的角色成为了将求取最少路由设备问题等价转换为朱刘-Edmonds算法求取最小生成树问题的关键纽带。这两个问题之间的转换在步骤5的具体实施方式中继续讨论。
[0036] 考虑到骨干路由器选择为朱刘-Edmonds算法的最小生成树的根时，需要将指向根节点的边权值皆删除，因此本步骤不添加无线设备指向骨干路由器的边，如图4所示。
[0037] 步骤4，对于步骤3生成的连通图，将所有添加的从骨干路由器出发的边的权重记为1；再以骨干路由器节点为根节点，使用朱刘-Edmonds最小生成树算法求得其最小生成树。
[0038] 具体的，首先寻找所有指向除根节点之外其他任意点的最小权重边，形成一个边集合；如果集合中存在环，则将环重构为一个新节点，并对指向新节点的边权重进行更新；重复将环化为边的操作，直至边集合中不再存在环；最后，在步骤3生成的原连通图找到进行过权重更新的边，进而找到这些边指向的点及其环，再在这些环中删除指向该点的环内最小边从而打断环，则得到以骨干路由器节点为根节点的最小生成树。
[0039] 将所有添加的从骨干路由器出发的边的权重记为1的目的在于，得到以骨干路由器为根节点的最小生成树之后，可以直接由根节点的出度得知步骤2的非连通图中含有多少个树，进而得出应将几个无线设备设置为路由设备，如图5所示。
[0040] 用数学语言可对朱刘-Edmonds最小生成树算法作如下描述：
[0041] 1.设有向图G＝(V，E)，其中V是有向图的点集，E是有向图的边集；选择一个点τ∈V作为根节点，对每个边ej∈E设其权重值为ωj；令T＝f(G，τ，W)表示有向图G中以τ为根节点，W＝∑ωj为值的生成树；其中，0＜j＜＝M，M为集合E的个数。
[0042] 2.对于有向图G，遍历除根节点τ之外的所有节点vi∈{V\{τ}}，对每个vi取指向vi的边中权重值最小边，并记录这些边的来源点pi，这些边的集合为P＝{(pi，vi)|vi∈{V\{τ}}；其中，0＜＝i＜N，N为集合V的个数。
[0043] 3.若P的任意子集不能构成环则得到最小生成树Tmin＝f(P，τ，W)，其值为W，算法结束。
[0044] 4.如果P中含有可以构成环的子集，则记环为C，并将环C抽象为点vc，并从P中删除C，即P←P\C；再在原图的边集E中找到指向环的边e＝(u，v)，即e满足 得到环外点u和环内点v；进而在环C中找到指向点v的边e′＝(u′，v)，即e′满足u′∈C∧v∈C；将点u指向抽象点vc的边记为ec＝(u，vc)，并将ec添加进P，即P←P\{ec}，ec的权重值ωc＝ω(e)-ω(e′)；如果有多条边可作为ec，则只选择ωc最小者加入P。
[0045] 5.重复计算2和计算4，直至P的任意子集不能构成环。
[0046] 6.考察计算4中的环C，找到P中的边ec在原图中相对应的边e，再在环C中找到和边e＝(u，v)指向相同点v的边e′＝(u′，v)；删除边e′以打断环，将环C中除了边e′以外的边加入P；最后从P中删除ec，将ec在原图中相对应的边e加入P，则得最小生成树Tmin＝f(P，τ，W)，其值为W，算法结束。
[0047] 从上述描述的计算2可以看出，整个算法排除了指向根节点的边，这也点出了步骤3没有必要添加从无线设备指向骨干路由器的边的缘由。
[0048] 步骤5，对于步骤4所生成的最小生成树，取其根节点的出度，设为K，则步骤2的非连通图所含树的最少个数与K相等，在最小生成树中取得直接与根节点相连的全部节点，并将这些节点作为路由设备节点即可。
[0049] 关于步骤2的非连通图所含树的最少个数与K相等，说明如下：
[0050] 首先，设非连通图所含树的最少个数为N，以步骤3的方式生成连通图并求得任意生成树后，设根节点出度为K′，为了保证连通性，必有K′＞＝N，否则根节点的出度不能保证连通所有互无交集的树；
[0051] 其次，考察步骤4所生成的任意生成树，设根节点出度为K*，由于生成树最终会将计算过程中生成的环还原为步骤2的非连通图的边集合中的元素，故必有K*＞＝K，其中K为最小生成树的根节点出度；
[0052] 综上，最小生成树的出度K取最小值，即K＝N。
[0053] 上述说明先表明了骨干路由器作为根节点的任意生成树需要满足的根节点出度条件，再表明任意生成树中的最小生成树的根节点出度最小，综合可知，最小生成树的根节点出度取最小值即非连通图所含树的个数。
[0054] 在实际应用中，过于追求最小数量的路由设备可能会造成某几个路由设备的负荷过重，影响整个无线网络的性能；故可以在求得最小数量路由设备的基础上，对于所含无线设备数量较多的树，酌情增加一两个路由设备以均衡通信负荷。图5之中也表现了这种情况。此外，在某些树中，一个路由设备可能难以满足树中所有现场设备与之单跳连接，此时可以将需要多跳连接的中继现场设备设置为兼容路由功能的设备，即该设备虽然是现场设备，但允许其数据链路层转发特定的某个邻居的信息，如此并不会带来许多额外的功耗和成本。
