ACO 结合 P2P 信任模型的无线传感器网络 Sinkhole 攻击检测

合尼古力·吾买尔

（新疆交通职业技术学院，新疆 乌鲁木齐 831401）

ACO 结合 P2P 信任模型的无线传感器网络 Sinkhole 攻击检测

合尼古力·吾买尔

（新疆交通职业技术学院，新疆 乌鲁木齐 831401）

针 对 无 线 传 感 器 网 络 中 的 Sinkhole 攻 击 问 题 ， 提 出 了 一 种 基 于 蚁 群 优 化 （ACO） 结 合 P2P 信 任 模 型 的Sinkhole 攻 击 检 测 （P-ACO） 算 法 。 首 先 ， 使 用 蚁 群 优 化 算 法 检 测 路 由 中 是 否 存 在 Sinkhole 攻 击 ， 并 生 成 传 感 器节点的警报信息；然后，利用布尔表达式进化标记生成算法为群组警报节点分发密钥，并使用密钥标记可疑节点；最后，计算可疑节点列表中各节点的信任值，将信任值低于预设阈值的节点视为攻击节点。 分析表明，相比二分查找算法与基于规则匹配的神经网络（RMNN）算法，该算法在匹配过程中需要更少的匹配搜索次数，提高 了 算 法 执 行 效 率 。 实 验 结 果 显 示 ， 相 比 RMNN 算 法 ， 该 算 法 可 以 更 加 准 确 地 检 测 Sinkhole 攻 击 。

无 线 传 感 器 网 络 ；Sinkhole 攻 击 ； 二 分 查 找 算 法 ； 蚁 群 优 化 ；P2P 信 任 模 型

1 引言

目 前 ，无 线 传 感 器 网 络 （wireless sensor network，WSN）［1］已在许多领域得到广泛应用。若不具备数据机密性和完整性 ，则 WSN 的 应 用 都 毫 无 意 义［2］，例 如 ，Sinkhole 攻 击［3］给WSN 应 用 带 来 了 较 大 的 挑 战 。参 考 文 献 ［4］提 出 了 一 种 基于 规 则 匹 配 的 神 经 网 络 （rules matching-based neural network，RMNN）算 法 ，可 有 效 检 测 Sinkhole 攻 击 ，然 而 ， 该算法中每个警报节点存储的密钥数量依赖于网络中警报节点的数量，因此增加了通信成本和内存开销。

本 文 提 出 了 一 种 结 合 蚁 群 优 化 （ant colony optimization，ACO） 和 P2P 信 任 模 型 的 攻 击 检 测 （P-ACO）算 法 ，用 来 检测 WSN 中 的 Sinkhole 攻 击 ，并 确 定 攻 击 节 点 。使 用 基 于 蚁群优化的攻击检测算法生成传感器节点的警报信息，在规则库中定义链路质量，传感器节点可根据规则库生成基于节点 ID 的警报信息，构建可疑节点列表，同时利用 P2P 信任模型计算可疑节点的信任度，从而确定攻击节点。实验结果验证了本文算法的有效性及可靠性。

2 系统架构

根 据 Sinkhole 攻 击 检 测 规 则［5］，每 个 传 感 器 节 点 的 本地检测引擎都存在一个规则库，规则库存储了相邻节点的ID 和每个 节点的链 路 质量，链 路 质量通过 本 地 数据分组监听模块监听相邻节点间的通信获得。图 1显示了攻击检测 系 统 模 型 ，用 来 检 测 Sinkhole 攻 击 。

图1 攻击检测系统

从 图 1 可 以 看 出 ，利 用 协 同 检 测引 擎 警 报 节 点 ，并 通过 节 点 相 互 通 信 来 交 换 可 疑 节 点 名 单 的 ID，随 后 使 用 ID检测攻击者。利用具有最小 布尔表达式 的 ACO 算法给警报节点分配密钥，用来标记可疑列表。然 后执行 P2P 信任模型计算可疑节点的信任值，将信任值低于阈值的节点作为攻击节点，并将该传感器节点从网络中移除。

本 文 提出的 P-ACO 算法主 要 分 为 3 步：检测 攻 击 ，通过 ACO 算 法 检 测 路 由 中 的 Sinkhole 攻 击 ；标 记 可 疑 节 点 ，如存在攻击，利用布尔表达式进化标记生成算法为群组警报节点分发密钥，并使用密钥标记可疑节点，获得可疑节点列表；识别攻击节点，通过 P2P 信任模型计算可疑节点信任值，从而确定攻击节点。

3 利用 ACO 检测 Sinkhole 攻击

ACO 检测系统模型如图 2 所示，通过系统中的蚁 群协同合作来获取最优解，蚁群中的蚂蚁移动时会留下信息素，用来和其他蚂蚁进行信息交换。蚁群智能代理有正位置和负 位 置 之 分 ，正 值 初 始 化 为 0，负 值 初 始 化为 节 点 ID数加1。正位置和负位置表示规则库搜索的位置范围。蚁群智能代理使用从正位置和负位置选择的随机数存储信息素。蚁群智能代理表示节点 ID 在规则库中的位置，该位置用于与路由更新数据分组发送端进行比较。

图2 蚁群系统模型

为了确定 路由更新数据分组发送端的节点 ID 是否 与规则库中的节点 ID 匹配，计算每个蚁群智能代理的能量 。蚁 群 智 能 代 理 通 过 比 较 规 则 库 中 的 节 点 ID（该 节 点 ID 用信息素表示）和路由更新数据分组发送端节点 ID 来计算能量值。

若两者的 ID 匹配，则能量值为 0 且停止该过程。若路由 更 新 数 据 分 组 节 点 ID 小 于 规 则 库 中 的 节 点 ID，则 能 量值为1且负位置的值被信息素代替，随后针对正位置和负 位 置 的 存 储 值 ，用 二 分 查 找［6］匹 配 路 由 更 新 数 据 分 组节 点 ID 和 规 则 库 中 的 节 点 ID。 如 果 输 入 数 据 分 组 节 点ID 大 于 用 信 息 素 表 示 的 节 点 ID， 则 能 量 值 为 +1 且 正 位置的值被信息素代替，随后针对正位置和负位置的存储值 ，用 二 分 查 找 匹 配 路由更新数据分组节点 ID 和 规 则库 中 的 节 点 ID。 如 果 路 由 更 新 数 据 分 组 发 送 端 节 点 ID与 规 则 库 中 的 节 点 ID 不 匹 配 ， 则 存 在 Sinkhole 攻 击 ，同时 节 点 生 成 警 报 。如 果 两 者 ID 匹配，则对应的 链路 质 量可 信 。算法 1 和 算法 2 分 别 显 示了二 分 查 找 算 法 和 ACO算法的伪代码。

设 Ai表 示 蚁 群 智 能 代 理 ，S（Nij）为 第 i个 智 能 代 理 规 则库 中 第 j个 位 置 的 节 点 ID，该 节 点 用 于 后 续 比 较 ，i=1，2，…，代理总数，j=1，2，…，规则集中的规则总数。S（P）表示更新数据分组发送端的节点 ID。根据式（1）计算能量值：

算法1 二分查找算法

算法 2 ACO 算法

分别初始化正位置和负位置值为 0 以及节点 ID 为+1；

选择用信息素表示规则位置的蚁群智能代理

根据能量函数计算蚁群智能代理 Ai的能量

4 标记可疑节点

4.1 警报节点表示

使用二叉树表示警报节点且通过节点标识符识别节点。属 于 群 组 的 警 报 节 点 表 示 为 ｛N1，N2，N3，… ，NN1｝，其 中 ，N1=2n，N1表示群组大小，n 表示群组中每个警报节点的二进制节点 标 识 符 （NID）的 长 度 。每 个 警 报 节 点 N 的 NID用 二 进 制 形式表示，n 个比特位 ID NID（N）=KnKn-1Kn-2，…，K1，其中，Ki要么为 0要么为 1。NID的布尔隶属 度函数 m（）用于确定群 组警报节点的 存 在 。如 果 N（KnKn-1Kn-2，… ，K1）=1，则 字 符 为 NID（KnKn-1Kn-2，…，K1）的节点为群组警报节点；如果 N（KnKn-1Kn-2，…，K1）=0，则字 符 为 NID（KnKn-1Kn-2，… ，K1）的 节 点 不 为 群 组 警 报 节 点 。

群组的每个警报节点都有群组密钥 SK 和辅助密钥集k1，k2，… ，kn，其 中 ，如 果 Ki=1，ki取 ki值 ；如 果 Ki=0，ki取 kij值 。辅 助 密 钥 对 应 于 NID中 的 二 进 制 位 。图 3 显 示 了 大 小 为4的群组中警报节点的密钥分布。群组中警报节点以真值表的形式表示，并使用最小布尔表达式寻找最小数量密钥来加密群组警报节点的群组密钥。表1显示了群组的真值，可以看出，警报节点 N1、N2、N3在群组中存在。

图3 群组警报节点的密钥分布

4.2 标记可疑节点的密钥分布

利 用 蚁 群 优 化 布 尔 表 达 式 进 化 标 记 生 成 （ant colony optimization Boolean expression evolvesign generation，ABXES）算 法［7］为 群 组 警 报 节 点 分 发 密 钥 。群 组 警 报 节 点 通过 真 值 表 表 示 。警 报 节 点 标 识 符 （NID）为 输 入 ，输 出 值 为 1表示群组中存在警报节点，输出值为 0表示群组中不存在警报节点。

表1 群组警报节点的真值

通过蚁群智能代理协作获取最优解决方案，每个蚁群智能代理通过信息素获取最优解。每个布尔表达式作为蚁群智能代理，该智能代理由“或（OR）”操作联合各自位置的 信 息 素 组 成［8，9］。图 4 描 述 了 在 两 个 变 量 情 况 下 智 能 代 理的表示方法。例如，在两个变量情况下，拥有信息素｛1，4｝的蚁群智能代理表示在位置 1和 4，使用 OR 操作联合对应位 置 表 达 式 K1和 表 达 式 K2＇。 因 此 ，信 息 素 ｛1，4｝表 示 布 尔表达式 K1+K2＇。

图4 2个变量情况下蚁群智能代理的表示方法

对有 n个变量的函数，智能代理表达式的最大数量为3n-1。一般情况下，对 有 n 个 变 量 的 表 达 式 ，表达式的数量和针对一个蚁群智能代理的位置数量定义如下：

为了找到智能代理最优解，需要计算智能代理的能量值，通过输出向量的比特位表示，通过布尔表达式计算该输出向量。设 Ai为蚁群智能代理，式（3）和式（4）分别给出了真值表输入向量和智能代理输出向量，利用式（5）计算代理能量。

其 中 ，count（wk=zk）为 实 例 的 数 量 ，wk与 zk等 价 。代 理信息素的能量值与最大群组对应的最小布尔表达式值相等。

最小布尔表达式获取的最小值表示分发给群组警报节点的辅助密钥的数量最小。使用每个警报节点的辅助密钥加密群密钥且分发给群组警报节点。算法 3显示了ABXES 算法伪代码。

算法 3 ABXES 算法伪代码

ABXES（）

K=0；

随机选择蚁群智能代理，表示信息素；

根据能量计算式计算每个智能代理 Ai能量；

if（代 理 能 量 等 于 群 组 警 报 节 点 最 大 数 量 ）then

return（代理的信息素表示布尔表达式）；

else

repeat

通过改变表达式更新信息素且计算代理能量值；

若当前代理能量值≥以前路由代理能量值，选择能量值大的代理信息素；

if （代 理 能 量 等 于 群 组 警 报 节 点 的 最 大 数 量 ）then

return（代理的信息素表示布尔表达式）；

end if

until （能 量 值 等 于 群 组 警 报 节 点 的 最 大 数 量 ）

end if

end ABXES

5 识别攻击节点

本文利用 P2P 信任模型计算可疑节点的信任值，从 而确定攻击节点。P2P 网络信任模型常用来评估节点的可信度［10］。其 通 常 根 据 5 个 因 素 来 计 算 节 点 的 可 信 度［11］：邻 居 节点对该节点的评价；给出评价的邻居节点的可信度；节点交易次数；与交易相关的因素；与交易相关的社会因素。节点u的信任值的计算式为：

其 中 ，T（u）为 节 点 u 的 信 任 值 ，S（u，i）为 节 点 u 第 i次交 易 所 获 得 的 评 价 ，p（u，i）为 与 节 点 u 进 行 第 i次 交 易 的 邻居 节 点 ，CR（p（u，i）为 节 点 p（u，i）对 节 点 u 的 评 价 的 可 信 度 ，TF（u，i）为在节点 u 的第 i次 交 易 中 ，与 交 易 相 关 的 因 素 （交易时间和交易额）对信任值的影响，α为交易因素的权重因子，β 为社 会因素的权重因子，CF（u）表示与 交易相关的社会因素（奖励机制）所产生的影响。

由于恶意节点可能会对与其交易的节点给出一个虚假评价，例如，恶意节点可能会对一个正常节点给出低信任度评价，需要对评价的可信度进行评估。P2P 信任模型中 通 常 有 2 种 对 评 价 进 行 可 信 度 评 估 的 机 制［12］：基 于 节 点的可信度；基于评价的相似度度量（PSM）。

本文信任模型 中 利 用 PSM 机 制 对邻居节 点 给 出的评价进行可信度评估。PSM 机制中，考虑了与节 点 u 进行交易的2个节点所给出的评价，并计算这 2个评价的相似度 ，相 似 度 越 高 ，表 明 该 评 价 可 信 度 越 高［13，14］。可 信 度 计 算式如式（7）所示。

其 中 ，Sim（p（u，i），w）为 节 点 w 和 节 点 p（u，i）给 出 评 价 的相似性，如式（8）所示。

其 中 ，IJS（p（u，i），w）为 节 点 w 和 节 点 p（u，i）与 节 点 u 的交 易 集 合 ，S（p（u，i），w）表 示 节 点 w 和 节 点 p（u，i）给 出 的 评 价向量，为两个评价向量的标准差。

群组中每个警报节点利用它们的辅助密钥解密群组密钥，并将结果存储在内存中。根据可疑节点 ID 和群组密钥生成消息认证代码。警报节点使用群组密钥标记消息，并将结果传输给群组中的其他警报节点。接收到消息认证代码的警报节点获取了群组密钥，通过比较内存中存储的群组密钥来确定可疑节点。根据 P2P 信任模型，计算可疑节点的信任值，将低于预设信任阈值的节点认定为攻击节点。

6 仿真实验

为了评估本文算法的有效性和优越性，利用基于OMNet++的 无 线 传 感 器 网 络 仿 真 器 Castalia 进 行 了 大 量 仿真［15］，设 置 节 点 分 散 在 50 m×50 m 的 正 方 形 区 域 内 ，节 点传送所有数据分组到位于区域中央的基站。仿真节点配置如 图 5 所 示 ，图 5（a）为 无 攻 击 时 的 网 络 结 构 ，而 图 5（b）为Sinkhole 攻 击 下 的 网 络 结 构 ，小 圆 圈 代 表 传 感 器 节 点 ，两 个节点之间的连接代表数据分组传输。将本文算法的性能与几 种 现 有 的 Sinkhole 攻 击 检 测 算 法 进 行 比 较 。

图5 两 种 情 况 下的 WSN 拓扑结构

6.1 匹配搜索次数比较

将本文算法的匹配搜索次数与对分查算法、RMNN 算法 进 行 比 较 ，WSN 中 传 感 器 节 点 分 别 取 100 、1 000 、10 000、100 000，记 录 各 个 算 法 的 最 佳 结 果 ，具 体 见 表 2。

表2 各个算法的匹配搜索次数

从表 2 可以看出，相比二分查找算 法、RMNN 算法，本文算法的匹配搜索次数均为最低，由于本文算法结合了ACO 与二分查找算法，二分查找匹配节点的数量减少，表明 ACO 在匹 配过程中需要更少的匹配时间，提高 了算法执行效率。

6.2 检测率比较

仿 真 环 境 分 别 由 100、1 000、10 000、100 000 个 随 机分布的节点组成，每次仿真中设定 25%的节点为恶意节点（25%），每 个 节 点 产 生 1 500 个 数 据 分 组 。每 个 模 拟 环 境进行 30 次仿真，置信区间为 95%。在 P2P 信任模型中，设定信任阈值为正常节点平均信任值的 50%。表 3 为各算法在存在恶意节点场景中的检测率。

表3 在不同节点数情况下的检测率

从 表 3 可 以 看 出，当 网 络 中 的 节 点 数 量 只 有 100 个时 ，2 种 算 法 的 攻击 检 测 率 均 为 100%；当 节 点 数 增 加 到1 000 个 时 ，本 文 算 法 的 检 测 率 仍 然 可 以 保 持 在 100%，而RMNN 算法的检测率则开始降低；节点数 增加 至 100 000个时 ，本 文 算 法 也 可 取 得 96%的 检 测 率 ，比 RMNN 算 法 高出 6%。 本 文 算 法 根 据 规 则 库 中 的 节 点 ID 来 识 别 异 常链 接 ，相 比 RMNN 算 法 ，能 够 更 加 准 确 地 检 测 Sinkhole攻击。

误报率表示攻击检测机制检测到攻击发生，但网络中并未发生攻击，而造成误报的主要原因是无线信道质量不稳定，误报率比较结果见表 4。

可以看出，本文算法的误报率较低，因为本文算法采用了 P2P 信任模型，信任值根据节点的行为和 邻居评价计算获得，是节点行为一贯表现的量化，因此基于信任的检测机制能够很好地避免因无线信道而产生的误报。

表4 在不同节点数情况下的误报率

7 结束语

为 了 检 测 WSN 中 Sinkhole 攻 击 并 识 别 WSN 中 的 攻击节点，本文提出了一种基于群体智能的入侵检测算法 — —P-ACO。 实 验 结 果 显 示 ， 相 比 经 典 的 匹 配 算 法 ，P-ACO 算 法 能 准 确 检 测 Sinkhole 攻 击 ， 不 会 产 生 误 检 ； 相比二分查找算法和 神经网络算法，P-ACO 算法匹配搜索次数更少 ，大大提高 了算法 执行 效率；相 比 RMNN 算法，P-ACO 算法 的内存需求 更低。 使用 ABXES 算法可以识别攻 击者节点 ，相比 RMNN 算 法 中 的单向散 列 函数和跳 数算法，减少了需要存储的密钥数量，节省了内存。利用 P2P信任模型进一步确定攻击节点，提高了检测准确度，降低了误报率。

未来将考虑引入其他优化算法，如粒子群优化、遗传算 法 等 ，在 其 他 Sinkhole 攻 击 环 境 下 进 行 实 验 ，进 一 步 改善算法的检测性能。

［1］ 叶 苗 ，王 宇 平. 一 种 新 的 容 忍 恶 意 节 点 攻 击 的 无 线 传 感 器 网络安全定位方法［J］. 计算机学报，2013，36（3）：532-545. YE M，WANG Y P.A new malicious nodes attack-resistant security location method in wireless sensor network ［J］.Chinese Journal of Computers，2013，36（3）：532-545.

［2］ 胡 蓉 华 ，董 晓 梅 ，王 大 玲.SenLeash：一 种 无 线 传 感 器 网 络 虫洞攻击约束防御机制［J］. 通信学报，2013，34（10）：65-75. HU R H，DONG X M，WANG D L.SenLeash：a restricted defense mechanism against wormhole attacks in wireless sensor network［J］.Journal of Communications，2013，34（10）：65-75.

［3］ ZHANG F J，ZHAI L D，YANG J C，et al.Sinkhole attack detection based on redundancy mechanism in wireless sensor networks［J］.Procedia Computer Science，2014，31（3）：711-720.

［4］ LU F，WANG L.Intrusion detection system based on integration of neural network for wireless sensor network［J］.Journal of Software Engineering，2014，8（4）：225-238.

［5］ ABDULLAH I，RAHMAN M M，ROY M C.Detecting sinkhole attacks in wireless sensor network using hop count ［J］. International Journal of Computer Network and Information Security （IJCNIS），2015，7（3）：50-57.

［6］ 李 睿 ，林 亚 平 ，易 叶 青 ，等. 两 层 传 感 器 网 络 中 安 全 Top-k 查询 协 议 ［J］. 计 算 机 研 究 与 发 展 ，2012，49（9）：1947-1958. LI R，LIN Y P，YI Y Q，et al.A secure Top-k query protocol in two tired sensor networks ［J］.Journal of Computer Research and Development，2012，49（9）：1947-1958.

［7］ MENDONCA M，AGUILAR J S，PEROZO N.An emergent ontology for ambient intelligence based on an ant colony optimization algorithm ［C］／Computing Conference （CLEI），September 15-19，2014，Montevideo，Uruguay.New Jersey：IEEE Press，2014：1-11.

［8］ WANG H Y，LIU Z Y，YING B U.Ant colony optimization algorithm for WSN cross-layer routing protocol ［J］.Journal of Changzhou University，2014.

［9］ 宋 立 新 ，戴 赫. 基 于 蚁 群 算 法 的 WSN 路 由 协 议 研 究 ［J］. 哈 尔滨理工大学学报，2014，42（6）：88-92. SONG L X，DAI H.Research on WSN routing protocol based on ant colony algorithm ［J］.Journal of Harbin University of Science and Technology，2014，42（6）：88-92.

［10］XIONG L，LIU L.Peertrust：supporting reputation-based trust for peer-to-peer electronic communities［J］.IEEE Transactions on Knowledge and Data Engineering，2004，16（7）：843-857.

［11］张 乐 君，邓 鑫，国 林，等. 基 于 关 联 度 分 析 的 WSN 节 点 信 任模 型 研 究［J］. 电 子 科 技 大 学 学 报，2015，34（1）：106-111. ZHANG L J，DENG X，GUO L，et al.A CMP energy consumption estimate model for computer systems ［J］.Journal of University of Electronic Science and Technology of China，2015，34（1）：106-111.

［12］蔡绍滨，潘虹杞，姚念民，等.基于云信任模型和蚁群算法的WSN 簇 可 信 路 由 算 法 ［J］. 软 件 学 报 ，2014，25（s1）：122-130. CAI S B，PAN H Q，YAO N M，et al.Cluster reliability routing algorithm based on cloud trust model and ant colony algorithm［J］. Journal of Software，2014，25（s1）：122-130.

［13］WANG M，XU Z，ZHANG Y，et al.Modeling and analysis of PeerTrust-like trust mechanisms in P2P Networks ［C］／Global CommunicationsConference （GLOBECOM），December3-7，2012，Anaheim，California，USA.New Jersey：IEEE Press，2012：2689-2694.

［14］LIU S，QI D，MENG J，et al.Study and implementation of wireless sensor networks collaboration based on bio-inspired trust and reputation model （BTRM）［J］.International Journal of Digital Content Technology&Its Applications，2012，6 （1）：53-66.

［15］LIN C，WU G.Enhancing the attacking efficiency of the node capture attack in WSN：a matrix approach ［J］.Journal of Supercomputing，2013，66（2）：989-1007.

Sinkhole attack detection based on fusion of ACO and P2P trust model in WSN

HENIGULI Wumaier
Xinjiang Vocational&Technical College of Communications，Urumqi 831401，China

For the Sinkhole attack problem of wireless sensor network （WSN），a detection algorithm based on fusion of ant colony optimization（ACO）and P2P trust model was proposed.Firstly，ant colony optimization algorithm was used to detect the existence of a Sinkhole attack in route and generate the alarm information of sensor nodes.Then，Boolean expression evolve sign generation algorithm was used to distributed keys for group alarm nodes，and it was used to mark suspicious nodes.Finally，P2P trust model was used to compute trust value of each suspicious node，and the node with trust value was lower than the preset threshold as invasion of node.The analysis shows that the proposed algorithm need less matching search times in matching process than binary search algorithm and the rules matching based neural network（RMNN）algorithm，which indicates that it has improved the efficiency of the algorithm. Experimental results show that the proposed algorithm has higher detection accuracy on Sinkhole attack than RMNN algorithm.

wireless sensor network， Sinkhole attack， binary search algorithm，ant colony optimization， P2P trust model

TP393

：A

10.11959／j.issn.1000-0801.2016089

2015-08-20；

2016-03-04

合尼古力·吾买尔 （1976-）， 女 （维吾尔族），新疆交通职业技术学院副教授，主要研究方向为网络安全、信息安全。