3.3 无线传感器网络入侵检测博弈模型

3.3.1 网络模型

根据入侵检测系统代理的安装位置，Farooqi等人[109]将无线传感器网络入侵检测系统分为三类：纯分布式（Purely Distributed）、纯集中式（Purely Centralized）和分布—集中混合式（Distributed-centralized）。在纯分布式无线传感器网络入侵检测系统中，入侵检测代理被安装于每个传感器节点并在本地检查相邻传感器节点的恶意行为。而在纯集中式网络结构中，入侵检测代理被安装于基站（Base Station）上，这种结构常需要额外的路由协议用来收集传感器节点的数据信息并以此分析传感器节点的行为。由于采用聚簇结构的无线传感器网络具有能耗和控制负荷低的特点，为适应这种网络结构，分布—集中混合式被引入进来，这种方式将入侵检测代理仅安装在“监控传感器节点”（Monitor Sensor Node）上，而“监控传感器节点”除执行入侵检测外，还具有与正常节点一样的转发数据功能。

本章采用的无线传感器网络入侵检测系统网络结构属于分布—集中混合式。但与入侵检测代理仅被安装在“监控传感器节点”上的情况不同，在本章采用的网络结构中，所有传感器节点都已部署入侵检测代理。与此同时，因为采用聚簇（Clustering）技术能显著改善网络生存期[110]，所以本章将聚簇技术用于无线传感器网络以便形成相互连接的层次结构。通过采用这种聚簇技术，所有的传感器节点都被分配到不同的簇中。每个簇都有一个称为簇头（Cluster Head，CH）的协调者和一些“成员传感器节点”。所有的簇头形成层次结构中的高层节点，而所有的“成员传感器节点”组成了低层节点。在这样的层次结构中，“成员传感器节点”通过“责任簇头”（Responsible CH）发送数据，“责任簇头”汇聚数据并通过其他的簇头将数据传输到基站。为了平衡簇头传感器节点的能量消耗，该节点经常需要定期更新。与无线传感器网络中的平面结构（Flat Architecture）相比，这种聚簇结构在减少能量消耗和降低通道碰撞方面具有显著的优点。当一个能量充沛的传感器节点被选中作为一个簇头时，驻留在簇头上的入侵检测代理将被同时启动，而处于“成员传感器节点”上的入侵检测代理将处于休眠状态。因此，簇头除汇聚和发送数据外，还有入侵检测的功能。图3-1给出了本章的网络模型。

在图3-1中，合法的传感器节点包括簇头和基站。“成员传感器节点”的类型可能是正常或恶意的。这些“成员传感器节点”知道它们自己的类型，但簇头不知道与它处于相同簇内的“成员传感器节点”类型。为适应这种网络环境，本章将采用信号博弈来描述“恶意成员传感器节点”的检测过程。当一个信号博弈被重复进行时，它可以被分为连续而独立的阶段，在每个阶段“成员传感器节点”和“簇头入侵检测代理”进行博弈的模型称为“阶段入侵检测博弈”。

3.3.2 阶段入侵检测博弈模型

定义3-1　“阶段入侵检测博弈”是一个五元组G＝（N，Θ，A，P，U），其中：

·N＝{“成员传感器节点”S，“簇头入侵检测代理”R}是一个包含两个参与者的集合。

·Θ＝ΘS×ΘR，其中ΘS＝{θS＝0，θS＝1}是“成员传感器节点”S的类型空间，ΘR＝{θR}是“簇头入侵检测代理”R的类型空间。

·A＝AS×AR，其中AS＝{AS（θS＝0），AS（θS＝1）}＝{{aS（θS＝0）｜Cooperate}，{aS（θS＝1）｜Attack，Cooperate}}是“成员传感器节点”S可用的动作集合，AR＝{aR｜Defend，Idle}是“簇头入侵检测代理”R可用的动作集合。

·P:Θ［0，1］是关于“成员传感器节点”S的推断（先验概率），P＝（p，1-p），其中，p表示“恶意成员传感器节点”（Malicious Member Sensor Node）的概率，而1-p表示“正常成员传感器节点”（Normal Member Sensor Node）的概率。

·U＝{（uS，uR）}，其中，uS:A×ΘR是“成员传感器节点”S的支付函数，uR:A×ΘR是“簇头入侵检测代理”R的支付函数，uS和uR的支付值如表3-1所示。

为反映无线传感器网络和入侵检测系统的特性，本章为“阶段入侵检测博弈”模型选择了一些特定的参数，当“恶意成员传感器节点”试图攻击无线传感器网络从而浪费其资源时，将影响无线传感器网络的正常运行，造成相邻节点通信的瘫痪，这个攻击过程将给“恶意成员传感器节点”带来收益，然而，它们也必须付出相应的成本用以支付它们的攻击。因此，对一个“恶意成员传感器节点”而言，本章引入gA和cA来分别表示攻击收益和成本。当一个“成员传感器节点”选择动作Cooperate时，意味着该节点能正常进行通信，也就是说，数据包能够被顺利地转发。这样，“正常成员传感器节点”将从具有良好通信保障的无线传感器网络中获取收益，而“恶意成员传感器节点”也将从它的伪装过程中获取收益。然而，在合作过程（即选择动作Cooperate）中，接收和转发数据包都会消耗传感器节点的能量。为了简单起见，本章假设“恶意成员传感器节点”和“正常成员传感器节点”将得到相同的收益和付出相同的成本。因此，对一个“成员传感器节点”而言，本章引入gC和cC分别表示选择动作Cooperate的收益和成本。当“簇头入侵检测代理”选择动作Defend时，它将获得收益gD，这是因为它成功地检测到了“恶意成员传感器节点”。与此同时，“簇头入侵检测代理”必须付出相应的成本cD用于支付能量的消耗。显然，与普通计算机网络中的入侵检测系统类似，“簇头入侵检测代理”中也存在检测率和误报率，本章分别用α和β表示。其中，存在误报率意味着“成员传感器节点”可能会在正常的通信中被误认为恶意节点，这对“簇头入侵检测代理”而言将造成损失lF。

在定义3-1给出的“阶段入侵检测博弈”模型中，总共有两个参与者，包括用θS表示的“成员传感器节点”S（发送者）和用θR表示的“簇头入侵检测代理”R（接收者）。“成员传感器节点”S可能是正常的也可能是恶意的，分别用θS＝0和θS＝1表示，这些类型信息对“簇头入侵检测代理”R而言都是私有信息。在每个阶段，每个参与者从它的动作空间中选择自己的动作，当“成员传感器节点”S是恶意时，它可能采取攻击或合作行为，采取合作是因为它想伪装自己以避免被监测到，也就是说，传感器节点类型θS＝1采取的动作aS（θS＝1）可能是Attack或者Cooperate。而当“成员传感器节点”S是正常节点时，它总是选择合作的行为，也就是说，类型θS＝0的动作aS（θS＝0）总是Cooperate。因此“成员传感器节点”S的动作空间AS（θS）可以表示为{Attack，Cooperate}。为了节省簇头节点的能量以便获得较长的生存期，“簇头入侵检测代理”R不应该总是选择动作Defend，也就是说，有时它应该选择动作Idle。这样传感器节点类型θR采取的动作aR（θR）可能是Defend或Idle。因此，“簇头入侵检测代理”R的动作空间是{Defend，Idle}。表3-1给出了“阶段入侵检测博弈”的支付矩阵。

在表3-1中，除了动作Idle外，都将产生成本。对于“动作对”（aS（θS＝1）＝Attack，aS（θR）＝Defend）而言，传感器节点类型θS＝1的支付等于未被检测到时的收益减去被检测到时的损失再减去攻击的成本，而传感器节点类型θR的支付等于成功检测到恶意节点的收益减去未检测到恶意节点的损失再减去检测的成本。对“动作对”（aS（θS＝1）＝Attack，aS（θR）＝Idle）而言，传感器节点类型θS＝1的支付等于攻击获得的收益减去攻击的成本，而传感器节点类型θR的支付等于被恶意节点攻击造成的损失。对“动作对”（aS（θS＝1）＝Cooperate，aR（θR）＝Defend）而言，传感器节点类型θS＝1的支付等于合作的收益减去合作的成本，而传感器节点类型θR的支付等于误报造成的损失减去采取动作Defend的成本。至于其他的“动作对”所产生的支付应该容易理解，在此不再赘述。

3.3.3 “阶段入侵检测博弈”的均衡

作为一种不完全信息动态博弈类型，“阶段入侵检测博弈”中的“簇头入侵检测代理”R虽然不知道“成员传感器节点”S的类型，但这种博弈模型仍能得到纯策略和混合策略贝叶斯均衡。当然，要得到这些均衡，首先需要通过海萨尼转换将“阶段入侵检测博弈”转化为完全但不完美信息动态博弈。在转化时，根据不完全信息动态博弈的时间顺序，一个虚拟的参与者“自然”（Nature）被引入进来，这个“自然”将首先行动并以一定的概率确定“成员传感器节点”S的类型。图3-2给出了转换后的“阶段入侵检测博弈”的扩展式。

定理3-1　当p＜（βlF＋cD）/（αgD＋αgA＋βlF）成立时，“阶段入侵检测博弈”存在纯策略贝叶斯均衡。

证明　（1）“成员传感器节点”S选择纯策略（aS（θS＝1）＝Attack，aS（θS＝0）＝Cooperate）。这种情况意味着当“成员传感器节点”S属于恶意节点时，总是选择动作Attack，而属于正常节点时总是选择动作Cooperate。因此，对“簇头入侵检测代理”R而言，选择Defend和Idle的期望收益分别是

和

如果EuR（Defend）≥EuR（Idle），也就是说

即

那么“簇头入侵检测代理”R的最优策略是采取动作Defend。然而，当“簇头入侵检测代理”R选择动作Defend时，Attack将不再是“成员传感器节点”S的最优动作，这是因为不等式

恒成立。因此，{（aS（θS＝1）＝Attack，aS（θS＝0）＝Cooperate），aR（θR）＝Defend}不是“阶段入侵检测博弈”的一个纯策略贝叶斯均衡。

如果EuR（Defend）＜EuR（Idle），也就是说

成立时，“簇头入侵检测代理”R的最优策略是采取动作Idle。相应地，Attack将成为“成员传感器节点”S的最优动作，这是因为不等式

恒成立。因此，{（aS（θS＝1）＝Attack，aS（θS＝0）＝Cooperate），aR（θR）＝Idle}是“阶段入侵检测博弈”的一个纯策略贝叶斯均衡。

（2）“成员传感器节点”S选择纯策略（aS（θS＝1）＝Cooperate，aS（θS＝0）＝Cooperate）。这种情况意味着不管“成员传感器节点”S是何种类型它总是选择动作Cooperate。对“簇头入侵检测代理”R而言，针对“成员传感器节点”S的动作Cooperate的最优响应是选择动作Idle，而对于“恶意成员传感器节点”θS＝1而言，针对“簇头入侵检测代理”R的动作Idle的最优响应是选择动作Attack。这样与纯策略（aS（θS＝1）＝Cooperate，aS（θS＝0）＝Cooperate）相互矛盾，因此，{（aS（θS＝1）＝Cooperate，aS（θS＝0）＝Cooperate），aR（θR）＝Idle}不是“阶段入侵检测博弈”的一个纯策略贝叶斯均衡。

综上所述，当

成立时，“阶段入侵检测博弈”存在纯策略贝叶斯均衡（（aS（θS＝1）＝Attack，aS（θS＝0）＝Cooperate），aR（θR）＝Idle）。这意味着“恶意成员传感器节点”总是会选择动作Attack并且“正常成员传感器节点”总是选择动作Cooperate，而“簇头入侵检测代理”R总是选择动作Idle。证毕。

虽然“阶段入侵检测博弈”存在纯策略贝叶斯均衡，但这与实际的防御要求不符，因为根据定理3-1，“簇头入侵检测代理”R总是选择动作Idle，这就是说，“恶意成员传感器节点”永远不会被捕获。因此仅得到纯策略贝叶斯均衡对“入侵检测博弈”是不够的，必须要找到能用于检测恶意传感器节点的混合策略贝叶斯均衡。

定理3-2　当条件p≥（βlF＋cD）/（αgD＋αgA＋βlF）成立时，“阶段入侵检测博弈”存在混合策略贝叶斯均衡。

证明　显然，由定理3-1，只有条件p≥（βlF＋cD）/（αgD＋αgA＋βlF）成立时，“阶段入侵检测博弈”才有可能存在混合策略贝叶斯均衡。

设“恶意成员传感器节点”θS＝1的混合策略为σS＝（ρ，1-ρ），其中，ρ表示“恶意成员传感器节点”采取动作Attack的概率。那么，“簇头入侵检测代理”R采取动作Defend和Idle的期望收益分别是

和

在“恶意成员传感器节点”θS＝1采取最优混合策略σ*S前提下，由“簇头入侵检测代理”R采取动作Defend和Idle的无差异性（Indifference）可以得到

因此，“簇头入侵检测代理”R的最优混合策略为

设“簇头入侵检测代理”R的混合策略为σR＝（δ，1-δ），其中，δ表示“簇头入侵检测代理”R采取动作Defend的概率。那么，“成员传感器节点”采取动作Attack和Cooperate的期望收益分别是

和

在“簇头入侵检测代理”R采取最优混合策略σ*R的情况下，由“成员传感器节点”S采取动作Attack和Cooperate的无差异性可以得到

因此，“成员传感器节点”S的最优混合策略为

综上所述，当条件成立时，“阶段入侵检测博弈”存在一个混合策略贝叶斯均衡（，aS（θS＝0）＝Cooperate），）。“阶段入侵检测博弈”存在混合策略贝叶斯均衡意味着当“簇头入侵检测代理”R以概率δ*采取动作Defend时，“恶意成员传感器节点”将以概率ρ*采取动作Attack而“正常成员传感器节点”总是选择动作Cooperate。证毕。

根据定理3-1和定理3-2，当“阶段入侵检测博弈”达到贝叶斯均衡时，“成员传感器节点”S和“簇头入侵检测代理”R在不同的概率p下都能选择它们各自不同的优化策略。从中可以看出，概率p实际上与“簇头入侵检测代理”的检测率α和误报率β有关。随着“推断”值的变大，由定理3-2中与概率p、检测率α和误报率β相关的混合策略贝叶斯均衡可知，“恶意成员传感器节点”选择动作Attack的概率越来越小。使用上述“阶段入侵检测博弈”的好处在于“簇头入侵检测代理”不必在每一个阶段选择动作Defend，这样簇头用于执行入侵检测代理的能量消耗就变小了。接下来要面临的一个新问题是在每一个独立的阶段如何确定一个合理的“推断”值p，这个“推断”值必须能根据实际的情况进行动态地更新。因此，本章根据无线传感器网络入侵检测的实际情况，进一步将“单阶段静态入侵检测博弈”扩展成“多阶段动态入侵检测博弈”，并且讨论其中的“推断”值是如何更新的。

3.3.4 多阶段动态入侵检测博弈模型

随着“成员传感器节点”S和“簇头入侵检测代理”R交互的进行，在每一个连续的阶段tk（k＝1，2，…，n；n∈Z＋），“阶段入侵检测博弈”将被重复地进行。为简化起见，本章假设“成员传感器节点”S与“簇头入侵检测代理”R在“阶段博弈”tk和“阶段博弈”tk-1具有相同的支付矩阵，也就是说，在“多阶段动态入侵检测博弈”中不存在收益的折扣现象。

根据贝叶斯规则，“簇头入侵检测代理”R可以从“阶段博弈”tk-1更新得到“阶段博弈”tk的“推断”值。设hS（tk）为“成员传感器节点”S的历史动作，aS（tk）为“成员传感器节点”S在“阶段博弈”tk的动作，p（θS＝1｜aS（tk），hS（tk））为“后验推断”。这里的“后验推断”表示在“阶段博弈”tk“成员传感器节点”是恶意节点的概率。

定义3-2　“簇头入侵检测代理”R的“后验推断”的计算式为

式中，p（θS｜hS（tk））为在历史动作hS（tk）下的“先验推断”；p（aS（tk）｜θS，hS（tk））为在“阶段博弈”tk中的“成员传感器节点”S在采取历史动作hS（tk）的前提下选择动作aS（tk）的概率。

由于任何的“簇头入侵检测代理”R都存在检测率和误报率，“簇头入侵检测代理”R从观测到的“成员传感器节点”S的动作中不一定能正确地反映实际的入侵检测现状。因此，本章在计算后验概率p（aS（tk）｜θS，hS（tk））时，将考虑检测率和误报率的影响，这些将分别由以下的式子得到，即

式中，1-α为负检测率；1-β为正误报率。

定义3-3　“多阶段动态入侵检测博弈”是一个五元组M＝（N，Θ，A，P（D），U），其中：

·N、Θ、A和U的定义与定义3-1中的N、Θ、A和U相同。

·P（D）＝（p（θS＝1｜hS（tk）），1-p（θS＝1｜hS（tk））），其中p（θS＝1｜hS（tk））表示“成员传感器节点”在阶段tk采取历史动作hS（tk）的前提下是恶意节点的概率，在“阶段博弈”tk结束时，其值将根据式（3-16）计算得到的p（θS＝1｜aS（tk），hS（tk））进行更新。

随着“推断”值的更新，“多阶段动态入侵检测博弈”将以序贯的方式进行，最后通过“完美贝叶斯均衡”表示“多阶段动态入侵检测博弈”的均衡。在整个博弈过程中，“成员传感器节点”S和“簇头入侵检测代理”R为最大化它们各自的效用，并不总是在每一个阶段博弈中采用相同的策略，并且随着“多阶段入侵检测动态博弈”的进行，它们的最优响应策略与可能改变的当前“推断”值相互独立。接下来，本章讨论如何得到“成员传感器节点”S的类型的“推断”值，并将利用得到的完美贝叶斯均衡得到“成员传感器节点”S和“簇头入侵检测代理”R的最优响应策略。在寻找“多阶段动态入侵检测博弈”的完美贝叶斯均衡之前，本章首先要说明该博弈模型满足必需的贝叶斯条件。

定义3-4[15]　贝叶斯条件包括：

B（i）　“后验推断”是相互独立的，并且参与者i的所有类型具有相同的“先验推断”。

B（ii）　“先验推断”到“后验推断”的更新通过贝叶斯规则实现。

B（iii）　参与者不传递任何参与者所不知道的事情信号。

B（iv）　“后验概率”在Θ上的共同的联合概率分布是一致的。

引理3-1　“多阶段动态入侵检测博弈”满足贝叶斯条件。

证明　因为“簇头入侵检测代理”R只有一种类型，因此B（i）满足。因为式（3-16）由贝叶斯规则得到，因此B（ii）满足。因为“成员传感器节点”S的信号由它的动作来决定，并且如果条件成立，那么，因此B（iii）满足。由于“多阶段动态入侵检测博弈”在任何阶段只有两个参与者，并且没有其他的参与者会影响“簇头入侵检测代理”R对“成员传感器节点”S的“推断”值的更新，因此B（iv）满足。证毕。

定理3-3　“多阶段动态入侵检测博弈”存在混合策略完美贝叶斯均衡。

证明　在“阶段博弈”tk，设“恶意成员传感器节点”在“阶段博弈”tk的策略为

式中，ρk为“恶意成员传感器节点”θS＝1选择动作Attack的概率。设“簇头入侵检测代理”R在“阶段博弈”tk的策略为

式中，δk为“簇头入侵检测代理”R采取动作Defend的概率。对“簇头入侵检测代理”R而言，在“阶段博弈”tk采取动作Defend和Idle的期望收益分别是

和

在“恶意成员传感器节点”θS＝1采取最优混合策略的情况下，由“簇头入侵检测代理”R采取动作Defend和Idle的无差异性可以得到

因此，“簇头入侵检测代理”R的最优混合策略为

对“恶意成员传感器节点”θS＝1而言，采取动作Attack和Cooperate的期望收益分别是

和

在“簇头入侵检测代理”R采取最优混合策略的情况下，由“恶意成员传感器节点”θS＝1采取动作Attack和Cooperate的无差异性可以得到

因此，“恶意成员传感器节点”θS＝1的最优混合策略为

综上所述，在“阶段博弈”tk存在混合策略完美贝叶斯均衡，其中和分别与检测率α、误报率β和“后验推断”p（θS＝1｜hS（tk））有关。证毕。

定理3-3表示在“多阶段动态入侵检测博弈”中，两个理性参与者“成员传感器节点”S和“簇头入侵检测代理”R将选择最优策略对。随着“多阶段动态入侵检测博弈”的进行，它们将各自根据定理3-3选择最优的动作以获取最大的利益。

3.3.5 基于完美贝叶斯均衡的入侵检测机制设计

根据“多阶段动态入侵检测博弈”的完美贝叶斯均衡，本章提出并设计了一种适合于无线传感器网络的入侵检测机制。图3-3给出了“成员传感器节点”S和“簇头入侵检测代理”R在入侵检测过程中进行的动作交互。

在图3-3中，基于完美贝叶斯均衡的入侵检测机制包括4个部分：存储数据区、管理者、“成员传感器节点”S和“簇头入侵检测代理”R。存储数据区主要用于存储“多阶段动态入侵检测博弈”涉及的参数gD、gA、cA、cC、cD、lF、α、β和p（θS＝1｜hS（tk））。因为“成员传感器节点”S可能是恶意或正常的节点，所以它可能会采取动作Attack或Cooperate，这些动作所产生的信息将会形成监控数据并发送到“簇头入侵检测代理”R。在“簇头入侵检测代理”R开始工作之前，管理员首先已配置好“簇头入侵检测代理”R的相应参数以便尽可能地使它工作得更加可靠和准确。在“簇头入侵检测代理”R中，入侵检测引擎能利用已有的异常和误用检测技术判断监控数据是恶意的还是正常的。然后“簇头入侵检测代理”R从存储数据区获得相应的博弈参数并初始化博弈模型，从而建立“阶段入侵检测博弈”。该博弈模型将接收来自入侵检测引擎中的输出数据和由管理者根据经验值设定的支付矩阵。其中，计算“簇头入侵检测代理”R要采取动作Defend的概率需要来自“阶段入侵检测博弈”的数据支持，其计算过程对整个入侵检测机制而言是一个关键步骤，这是因为根据定理3-3，得到就能确定“簇头入侵检测代理”R将以何概率选择动作Defend和Idle。最后，“簇头入侵检测代理”R将计算p（θS＝1｜aS（tk），hS（tk）），并据此更新p（θS＝1｜hS（tk））后存入存储数据区，以备下一“阶段入侵检测博弈”使用。这样经过反复迭代，形成的“多阶段动态入侵检测博弈”被用于决定“簇头入侵检测代理”R何时启动的策略。

下面给出基于完美贝叶斯均衡的无线传感器网络入侵检测代理何时启动最优策略算法。

算法3-1　无线传感器网络入侵检测代理何时启动最优策略算法。