一种基于互信息量的监测路由器选择方法

摘要

本发明一种基于互信息量的监测路由器选择方法，属于通信网络技术领域；该方法首先获得每个路由器的桥连接系数，其次获得每个路由器与每个路由器所有相邻路由器的互信息总量，将互信息总量最大的路由器选定为网络拓扑中的监测路由器，最后确定每个监测路由器的监管区域；本发明所选取监测路由器的拓扑位置在网络中具有重要地位，便于互通监测信息，能够保证监测信息的准确性，不易受到攻击；本发明避免了基于簇的入侵监测系统监测方法忽略路由器在网络中的重要性差异以及网络路由器之间的相互联系，所导致的过度地消耗路由器的计算资源和能量，减少了冗余信息，避免资源消耗，减少系统监测开销，在很大程度上提高了网络性能。

说明书

技术领域

本发明属于通信网络技术领域，具体涉及一种基于互信息量的监测路由器选择方法。

背景技术

无线Mesh网络是一种基于多跳互联的新型无线网络，它不同于传统的无线局域网，也 不同于无线多跳的Ad Hoc网络，可以看作是两种网络的；无线Mesh网络的节点同时具有路 由器和中继的功能，节点之间可以实现互联，类似于Ad Hoc网络，具有自组织、自配置等 特性，无线Mesh网络由Mesh路由器构成的骨干网络和由Mesh客户端构成的对等网络组成。 无线骨干网由无线Mesh路由器组成，只具有少量移动性或不具有移动性，能够提供无线回 程功能；无线骨干网的路由位置固定，有固定电源供电的基础设施，受能量限制小；Mesh客 户端和传统客户端通过骨干网络提供的服务访问其他网络，可以实现无线Mesh网络与互联 网、蜂窝网、传感器网络等网络的接入功能。

无线链路的使用虽然提供了极大的方便，但同时也带来了很多安全威胁，对无线Mesh 网络安全问题的研究具有重要意义；入侵监测系统作为一种主动的安全防护技术，能够针对 内部和外部节点的攻击实时地进行防护，及时地做出相应响应以减少损失；入侵监测的重要 任务是监测网络路由器的状态，观察路由器行为是否正常，若将网络中每个路由器都作为入 侵监测系统的监测路由器，即采用全网部署入侵监测系统算法，大量冗余信息的计算将带来 巨大的资源消耗；反之，若监测路由器选择的太少，入侵监测系统则可能完成不了对网络中 所有路由器的监测任务。

目前的网络监测路由器选择方法一般只考虑路由器的拓扑位置，将拓扑位置相近的路由 器分到一“簇”；这些方法忽略了路由器在网络中的重要性差异以及网络路由器之间的相互联 系，因此有可能使得联系来往频繁、通信频率高的路由器被分到不同的“簇”内，使得它们 所在簇的簇首会处理很多相同或相似的信息，过度地消耗了路由器的计算资源和能量，同时 也增加了系统的安全监测开销主并且它们很有可能在同一时刻监测出恶意节点信息，同时发 送报告通知全网相关节点，因此监测开销的波动性也大，使得网络性能下降。

发明内容

针对现有技术的不足，本发明提出一种基于互信息量的监测路由器选择方法，以达到减 少冗余信息、避免资源消耗、降低系统监测开销和提高网络性能的目的。

一种基于互信息量的监测路由器选择方法，包括以下步骤：

步骤1、根据网络拓扑中每个路由器的出度与其相邻路由器的出度，获得每个路由器的 桥连接系数；

步骤2、根据每个路由器的桥连接系数与其相邻路由器的桥连接系数，获得每个路由器 与其相邻路由器的互信息量，进一步获得每个路由器与其所有相邻路由器的互信息总量，将 互信息总量最大的路由器选定为网络拓扑中的初始监测路由器；

步骤3、确定初始监测路由器的监管区域，具体步骤如下：

步骤3.1、设定初始监测路由器的影响力边权值阈值，并确定初始监测路由器的初始监管 区域范围，所述初始监管区域范围为初始监测路由器的最大跳数所构成的范围；

步骤3.2、获得初始监测路由器对其初始监管区域范围内每个路由器的影响力边权值，判 断上述影响力边权值是否大于所设定影响力边权值阈值，若是，执行步骤3.3，否则，执行步 骤4；

步骤3.3、将影响力边权值大于所设定阈值的所有路由器设定为初始监测路由器的最终监 管区域，并且上述路由器不再作为下一个监测路由器和下一个监测路由器监管区域的选择对 象；

步骤4、判断是否网络拓扑中所有路由器均被监管到，若是，执行步骤7，否则，执行步 骤5；

步骤5、选定网络拓扑中的下一个监测路由器，具体步骤如下：

步骤5.1、确定下一个监测路由器的选定范围，即初始监测路由器所监管的每个边缘路由 器向监管区域外最大跳数所构成的范围，作为下一个监测路由器的选定范围；

步骤5.2、在下一个监测路由器的选定范围内，根据步骤1和步骤2，获得每个路由器的 互信息总量；

步骤5.3、对第一跳路由器的互信息总量进行权值处理，获得权值处理后的互信息总量， 所述第一跳路由器为：初始监测路由器所监管每个边缘路由器向监管区域外第一跳的每个路 由器；

步骤5.4、将第一跳路由器权值处理后的互信息总量与选定范围内剩余路由器的互信息总 量进行对比，将互信息总量最大的路由器选定为网络拓扑中的下一个监测路由器；

步骤6、返回执行步骤3，获得网络拓扑中下一个监测路由器的监管区域；

步骤7、将所有选定的监测路由器设定为网络拓扑中的监测路由器，每个监测路由器监 管其监管区域内的路由器。

步骤1所述的获得每个路由器的桥连接系数，采用以下公式：

$B\left(v\right)=\frac{d{\left(v\right)}^{-1}}{\underset{i\in N\left(v\right)}{\Sigma }\frac{1}{d\left(i\right)}}---\left(1\right)$

其中，B(v)表示路由器v的桥连接系数，即表示路由器v的拓扑位置重要性，d(v)表示 路由器v的出度，v表示第v个路由器，i表示第i个路由器，N(v)表示与路由器v相邻的路 由器集合，d(i)表示路由器i的出度。

步骤5.3所述的对第一跳路由器的互信息总量进行权值处理，获得权值处理后的互信息 总量，具体为：设定互信息量参数，所述互信息量参数为0到1之间的一个数值，将该路由 器的互信息总量与所设定的互信息量参数相乘，即为权值处理后的互信息总量。

本发明的优点：

本发明一种基于互信息量的监测路由器选择方法，所选取的监测路由器的路由器具有以 下的性质：拓扑为置在网络中具有重要地位，能够与更多的路由器进行直接或者间接通信并 有紧密联系，便于互通监测信息；其次，这些路由器获得的信息可信度高，能够保证监测信 息的准确性，不易受到攻击；本发明避免了基于簇的入侵监测系统监测方法忽略路由器在网 络中的重要性差异以及网络路由器之间的相互联系，所导致的过度地消耗路由器的计算资源 和能量，减少了冗余信息，避免资源消耗，减少系统监测开销，在很大程度上提高了网络性 能。

附图说明

图1为本发明一种实施例的网络拓扑结构示意图；

图2为本发明一种实施例的基于互信息量的监测路由器选择方法流程图；

图3为本发明一种实施例的监测开销对比图。

具体实施方式

下面结合附图对本发明一种实施例做进一步说明。

本发明实施例中，采用随机产生的路由器数量为30无线Mesh网络，网络拓扑结构示意 图如图1所示，拓扑中30个路由器均为无线路由器，所述的无线路由器是单射频，无线链 路之间互不干扰；

本发明实施例中，一种基于互信息量的监测路由器选择方法，方法流程图如图2所示， 包括以下步骤：

步骤1、根据网络拓扑中每个路由器的出度与其相邻路由器的出度，获得每个路由器的 桥连接系数；

本发明实施例中，所述的获得每个路由器的桥连接系数，采用以下公式：

$B\left(v\right)=\frac{d{\left(v\right)}^{-1}}{\underset{i\in N\left(v\right)}{\Sigma }\frac{1}{d\left(i\right)}}---\left(1\right)$

其中，B(v)表示路由器v的桥连接系数，即表示路由器v的拓扑为置重要性，d(v)表示 路由器v的出度，v表示第v个路由器，i表示第i个路由器，N(v)表示与路由器v相邻的路 由器集合，d(i)表示路由器i的出度；

步骤2、根据每个路由器的桥连接系数与其相邻路由器的桥连接系数，获得每个路由器 与其相邻路由器的互信息量，进一步获得每个路由器与其所有相邻路由器的互信息总量，将 互信息总量最大的路由器选定为网络拓扑中的初始监测路由器；

本发明实施例中，获得每个路由器与其相邻路由器的互信息量，采用以下公式：

其中，I(i,j)表示路由器j对路由器i的互信息，B(i)表示路由器i的桥连接系数，B(j)表 示路由器j的桥连接系数，j表示第j个路由器；

本发明实施例中，进一步获得每个路由器与其所有相邻路由器的互信息总量，采用以下 公式：

$I\left(i\right)=\underset{j\in N\left(i\right)}{\Sigma }I(i,j)---\left(3\right)$

其中，I(i)表示路由器i与路由器i所有相邻路由器的互信息总量，N(i)表示与路由器i相 邻的路由器集合；

本发明实施例中，获得网络拓扑中每个路由器的桥连接系数，和每个路由器与每个路由 器所有相邻路由器的互信息总量如表1所示：

表1

路由器编号 桥连接系数 互信息总量值 路由器1 0.0857 -1.8918 路由器2 0.1780 0.4012 路由器3 0.3684 1.5698 路由器4 0.1780 0.4012 路由器5 0.1991 1.1643 路由器6 1.2000 1.7423 路由器7 0.0993 -2.9632 路由器8 0.1156 -0.1293 路由器9 0.2825 1.6416 路由器10 0.2717 1.5510 路由器11 0.1062 -1.6292 路由器12 0.3064 2.1203 路由器13 0.1407 -0.0020 路由器14 1.7143 2.5095 路由器15 0.0761 -3.2687 路由器16 0.1062 -1.6292 路由器17 0.1446 0.7874 路由器18 0.1154 -0.2440 路由器19 0.0857 -1.8918 路由器20 0.1407 -0.0020 路由器21 0.1522 0.7257 路由器22 0.2625 0.5482 路由器23 0.1154 -0.2440 路由器24 0.1719 0.1075 路由器25 0.1004 -1.5842 路由器26 0.1174 -0.1276 路由器27 0.2825 1.6416 路由器28 0.1194 -1.0513

路由器29 0.0916 -1.8230 路由器30 0.3684 1.5698

本发明实施例中，从表1可以看出，路由器14的互信息总量最大，将路由器14选定为 网络拓扑中的初始监测路由器；

步骤3、确定初始监测路由器的监管区域，具体步骤如下：

步骤3.1、设定初始监测路由器的影响力边权值阈值，并确定初始监测路由器的初始监管 区域范围，所述初始监管区域范围为初始监测路由器的最大跳数所构成的范围；

本发明实施例中，设定初始监测路由器的影响力边权值阈值为0.1，设定初始监测路由器 的初始监管区域范围为初始监测路由器14进行3跳所构成的范围；

步骤3.2、获得初始监测路由器对其初始监管区域范围内每个路由器的影响力边权值，判 断上述影响力边权值是否大于所设定影响力边权值阈值，若是，执行步骤3.3，否则，执行步 骤4；

本发明实施例中，所述获得初始监测路由器对其初始监管区域范围内每个路由器的影响 力边权值，采用以下公式：

$\sigma \left(s_{i}w\right)=\underset{W\left(s_{i}w\right)}{\Sigma }\left(\underset{\mathrm{uv}\in M\left(s_{i}w\right)}{\Pi }{\mu }_{\mathrm{uv}}\right)---\left(4\right)$

其中，σ(s_iw)表示第i个监测路由器到路由器w的影响力边权值，W(s_iw)表示第i个监测 路由器到路由器w的所有路径，s_i表示第i个监测路由器，w表示第w个路由器，M(s_iw)表 示第i个监测路由器到路由器w的一条路径上的所有路由器集合，μ_uv表示路由器u对其相邻 路由器v的影响力边权值，即路由器u与其相邻路由器v之间链路的影响力边权值，u表示第u 个路由器；

其中，N(u)表示与路由器u相邻的路由器集合，d(u)表示路由器u 的出度；

本发明实施例中，获得初始监测路由器14对其初始监管区域范围内每个路由器的影响力 边权值如表2所示：

表2

步骤3.3、将影响力边权值大于所设定阈值的所有路由器设定为初始监测路由器的最终监 管区域，并且上述路由器不再作为下一个监测路由器和下一个监测路由器监管区域的选择对 象；

本发明实施例中，从表2可以看出，初始监测路由器14对路由器1、路由器7、路由器 8、路由器17、路由器18、路由器19和路由器29的影响力边权值均大于所设定阈值0.1，将 上述所有路由器设定为初始监测路由器14的最终监管区域，并且上述路由器不再作为下一个 监测路由器和下一个监测路由器监管区域的选择对象；

步骤4、判断是否网络拓扑中所有路由器均被监管到，若是，执行步骤7，否则，执行步 骤5；

本发明实施例中，网络拓扑中存在未被监管路由器，执行步骤5；

步骤5、选定网络拓扑中的下一个监测路由器，具体步骤如下：

步骤5.1、确定下一个监测路由器的选定范围，即初始监测路由器所监管的每个边缘路由 器向监管区域外最大跳数所构成的范围，作为下一个监测路由器的选定范围；

本发明实施例中，设定下一个监测路由器的选定范围为：初始监测路由器14所监管的每 个边缘路由器均向监管区域外进行2跳所构成的范围，作为下一个监测路由器的选定范围；

本发明实施例中，初始路由器14监管区域外的所有路由器均在下一个监测路由器选定范 围内；

步骤5.2、在下一个监测路由器的选定范围内，根据步骤1和步骤2，获得每个路由器的 互信息总量；

步骤5.3、对第一跳路由器的互信息总量进行权值处理，获得权值处理后的互信息总量， 所述第一跳路由器为：初始监测路由器所监管每个边缘路由器向监管区域外第一跳的每个路 由器；

本发明实施例中，采用公式I'＝ε·I对第一跳路由器的互信息总量进行权值处理，其中I' 表示权值处理后的互信息总量，ε表示互信息量参数，即与每个路由器的互信息量有关的值， 本发明实施例中ε设定为0.9，I表示权值处理前的互信息总量；

步骤5.4、将第一跳路由器权值处理后的互信息总量与选定范围内剩余路由器的互信息总 量进行对比，将互信息总量最大的路由器选定为网络拓扑中的下一个监测路由器；

步骤6、返回执行步骤3，获得网络拓扑中下一个监测路由器的监管区域；

步骤7、将所有选定的监测路由器设定为网络拓扑中的监测路由器，每个监测路由器监 管其监管区域内的路由器。

本发明实施例中，选定的所有监测路由器及每个监测路由器的监管区域如表3所示：

表3

监测路由器编号 监管区域路由器编号 路由器6 22、28 路由器10 2、4、5、21 路由器12 15、23、24、25、26 路由器14 1、7、8、17、18、19、29 路由器27 9、13、20 路由器30 3、11、16

本发明实施例中，采用传统的基于分簇的监测路由器选择方法获得监测路由器和每个路 由器的监管区域如表4所示：

表4

种子节点编号 监管区域节点编号 节点1 9、13、18、19、20、23、26、27、29 节点12 无 节点14 无 节点17 7、8、11、16、21、28 节点22 6 节点25 2、4、5、10、15、24 节点30 3

本发明实施例中，通过表3和表4可以看出，基于互信息量的监测路由器选择方法选定 了6个监测路由器，传统的基于分簇的监测路由器选择方法选定的监测路由器数目为7，两 种算法选出的监测路由器数目相差不多，但从表4中可以看出，传统的基于分簇的监测路由 器选择方法的路由器分配不合理，监测路由器1需要监测9个路由器，占路由器总数目的1/3 左右，而有的路由器只负责监测很少路由器甚至只负责监测路由器本身信息，不负责监测其 他路由器，如路由器12、14、22、30等；基于互信息量的监测路由器选择方法，路由器分配 较合理，虽然部分监测路由器监测的路由器也较多，但不局限在一跳内的邻居路由器，该算 法以信息相似度作为分配原则，将路由器信息相似的路由器分配到同一个路由器，减少了系 统的监测开销，避免监测信息的过度消耗；

本发明实施例中，如图3所示，对基于互信息量的监测路由器选择方法、传统的基于分 簇的监测路由器选择方法和全网部署入侵监测系统算法的监测开销进行比较，图中“—·—” 为基于互信息量的监测路由器选择方法的监测开销，“—□—”为传统的基于分簇的监测路由 器选择方法的监测开销，“—|—”表示全网部署入侵监测系统算法的监测开销，监测系统采 用基于互信息量的监测路由器选择方法选择监测路由器时，其监测开销明显低于其他两种对 比算法，与传统的基于分簇的监测路由器选择方法相比，基于互信息量的监测路由器选择方 法的监测开销减少了约25％，而且开销维持在一种较稳定的状态，因此基于互信息量的监测 路由器选择方法在很大程度上提高了网络性能。