无线传感器网络中的分簇行为信任管理系统

（一）信任管理系统

由于身份信任不能解决由内部具有合法身份的妥协节点发起的攻击，行为信任被引入作为无线传感器网络安全的必要补充。在不与身份信任混淆的情况下，行为信任也可简称为信任，它是评估主体对评估客体随着其行为的变化不断修正的在某一领域的评价。这取决于评估客体的历史行为经验。信任的评估有简单的加权相加法。以Audun为代表的一些学者提出了基于Beta函数和基于主观逻辑的信任模型，部分现有的文献则研究了模糊信任模型。在不同的应用领域适用不同的信任模型。

本研究基于分簇的无线传感器网络。这也是目前应用最为广泛的无线传感器网络模式。在分簇的无线传感器网络中，网络被划分为多个簇，簇头节点负责在簇内收集并融合数据并将融合结果转发给下一跳簇头节点，通过适当的路由最终将数据转发至基站。在分簇的无线传感器网络中，信任主要包括数据包转发信任、路由信息信任、数据可靠性信任、声明可靠性信任、定位信息发布信任等各个方面，也可以应用在不同的上下文环境中。判定节点是否可信是要根据自己的观察和其他节点的推荐综合计算出具体的信任度量值。各种上下文环境下的信任值的量化方法有基于主观逻辑、基于概率方法和基于模糊集理论等多种方法。在信任系统的支持下，根据节点间的信任关系，便于节点选择适当的安全措施，并就安全问题做出正确的决策。

1.身份信任与行为信任

信任目前还没有非常统一的定义，国际电信联盟X.509规范认为：在一定的上下文环境中，如果一个实体能够按照与另一个实体预先的约定完成某项事件，那么认为后一个实体信任前一个实体。信任关系包括身份信任和行为信任两种。身份信任关系是通过密钥机制、基于身份的访问控制等方法建立的，验证网络实体的可信性，从而决定其是否具有对网络某种操作的权利。身份信任关系是静态的。下面给出具体的行为信任关系的定义。

行为信任：是指评估主体通过对评估客体行为的监控，根据其在某一上下文环境中的历史行为表现而做出的对其可信度和有效性的评价。可以通过划分等级来进行行为信任的量化标识。当评估客体的行为改变时，根据自身监测和经验，评估主体所做出的信任评价也会随之发生改变。行为信任关系是动态的。行为信任关系的建立基于实体之间的历史相互作用所产生的证据。实体间的信任关系随着时间的推移也在不断变化。在基于行为的信任模型中，当一个评估客体的行为发生变化时，评估主体将会更新对该评估客体的信任评价值。因此，行为信任关系是动态的。如果实体的历史行为忠于协议，则实体之间的信任将增加。反之，则实体之间的信任将减少。

行为信任是与上下文相关的。设节点A为信任主体，节点B为信任客体。节点A可能非常信任节点B提供的数据包转发能力，但不一定信任它提供数据的可靠性。因为信任是动态的，所以信任也是有时效的。每个不同时刻节点A对节点B的信任程度也不一定是相同的。行为信任是非对称的。信任主体节点A信任节点B，并不代表节点B信任节点A。节点A信任节点B的程度也并不等于节点B信任节点A的程度。行为信任是有时效的。信任主体节点A在某一时刻信任节点B并不等同于节点A在另一时刻也同等程度地信任节点B。随着时间和交互次数的增多，节点A对节点B的信任水平可能发生较大改变。

2.信任与声望

根据节点行为是否是被直接观测或交互作用过，信任通常被分为直接信任和间接信任。间接信任可表现为其他节点的推荐的观测结果或是多个节点观测结果的综合结果，分别称之为推荐信任和声望。

直接信任、推荐信任和声望的定义分别如下。

直接信任：节点A根据与信任的目标节点B的直接互动经验或历史信息而形成的有关目标节点B的在一定上下文环境下，一定时间内的能力、诚实度、可靠性等方面的主观判断。直接信任关系的量化表示或等级划分称为直接信任度。

推荐信任：节点A向其他某节点C请求并反馈回来的在一定上下文环境下，一定时间内，关于节点B的能力、诚实度、可靠性等方面的可信度评价。

声望：在一定上下文环境下，一定时间内，其他节点对节点B的能力、诚实度、可靠性等方面的综合可信度评价。声望是其他节点在过去与之交互的过程中所积累的对其可信度的综合评价，即节点的综合信任值。声望的最后一次更新时间与节点参与的转发次数都会影响声望的可靠性和准确性。

信任和推荐信任是一个评估主体对评估客体的基于其历史行为所做出的主观判断和主观判断的传递，而声望则是一定范围内的多个评估主体对某一个评估主体的总体评价，表示了一定范围内的多个节点对该评估客体的综合信任程度。信任是局部的概念，具有主观性，仅仅发生在两个节点之间。而声望是网络中一定范围内多个评估主体对某个评估客体在某一领域评价的综合，具有一定的客观性和全局性。

3.信任度的评估方法

信任度的评估值值域可以是连续的区间如（0，1），也可以是离散的多个值分别代表不同程度的信任度。每个节点的信任度可以用一个精确的值表示，也可以用模糊向量来表示，目前常见的信任度测评估算法主要有以下四点。

（1）简单相加法或加权相加法。简单相加法是对于节点行为的每一个的评估值进行简单的相加求和。加权相加法对每一条证据相加时，给予不同的证据不同的权值。

（2）基于概率密度函数的评估算法。在该算法中，采用0～1之间的概率值来表示网络中节点之间的信任度。1表示完全信任，0表示完全不信任。取值越大的节点的可信度越高。该算法以二项事件（节点观察到的肯定事件和否定事件）的后验概率的Beta分布函数为基础，通过对概率密度函数进行统计计算，并结合原有的信任值与新的信任度评价来计算并更新节点的信任值。

（3）基于主观逻辑的评估算法。使用主观逻辑对信任关系进行评估和描述，将证据空间和观念空间引入信任模型中，利用一个包含信任、不信任、不确定的三元组描述实体的主观信任度。

（4）基于模糊逻辑的信任计算方法。应用模糊理论，将不宜精确描述的信任度模糊化，并利用模糊逻辑得到实体对各个级别信任层次的信任向量。在不同的上下文环境下，对于不同的监测事件属性，可用不同的方法来表示和评估节点的信任程度，并为信任决策提供支持。

4.无线传感器网络的信任管理系统

信任管理系统一般由三个部分组成：①信任信息获取：主要负责收集信任客体的行为信息，并由这些历史行为信息决定信任主体对信任客体的信任度。②信任信息存储与处理：信任管理系统需要解决的一个重要问题是信任信息的安全存储。与信任客体节点有过交互的节点将计算或更新该信任客体节点的信任度。信任计算可以采用不同的评估模型。③依据信任信息的行动决策：网络中的节点通过信任管理系统得到信任客体节点的信任后，可依据一定的预定策略采取的相应的行动，如选择路由信任度高的节点转发数据包，将节点的数据融合声望度作为一个簇头节点的选举因素等。信任客体节点在各上下文环境下的信任度可以帮助网络中的其他节点确定它在各相应应用中的行动决策。目前，在无线传感器网络中的信任管理系统主要有以下几种分类方式。

（1）层次型信任管理与平面型信任管理。信任值的处理具有层次性。信任关系的建立，信任值的传递以及信任值的存储等都与网络的拓扑结构有关系。层次式信任管理中，信任管理的上层节点存储所有下层节点或者相邻节点的信任值。在分簇的WSN中，形成基站—簇头节点—普通簇内节点的3层信任管理。平面式信任管理是网络中没有明显的中心节点和层次结构，所有的节点地位是平等的，因而采取相同的信任计算模型和相同的信任传递和信任存储管理策略。

（2）基于声望的全局信任管理。在进行信任评估时，综合考虑其他节点的信任评估值并依此更新和管理。在基于声望的全局信任管理中，节点在整个网络中具有唯一的信任值；此类管理方式主要用于在分簇结构的网络中的骨干网络。本地信任管理是指信任主体节点根据本地存储的信任值或是综合邻居节点发送的推荐信任做决策。信任客体节点在不同信任评估节点处的信任值可能并不一致。

（3）通用信任管理。其是指对评估客体在不同上下文环境下的历史行为表现进行综合监测和评价的信任管理框架。其节点的信任计算需要对评估客体节点在各个不同上下文环境下的表现进行综合考虑，是对该评估客体节点可信性的综合评估。应用相关信任管理是面向特定应用的信任管理，例如路由、数据融合、数据管理、定位等具体应用。由于无线传感器网络不同的上下文环境中，如路由、数据融合等的信任信息采集、更新和存储要求不同，所以适用于应用相关的信任管理。

（二）博弈论

1.博弈论定义

博弈论（Game Theory）是研究多个决策主体在其行为发生直接相互作用时，如何各自做出理性的决策，并在各自的策略之间达到均衡的问题的。也就是说，一个行为主体的行为决策受到其他行为主体的策略选择的影响。同时，该行为主体的决策也会影响到其他主体的策略选择。从这个意义上讲，博弈论又称为“对策论”。1944年，冯·诺依曼等人将二人博弈推广到n人博弈，并将博弈论系统地应用于经济领域，这标志着现代博弈理论的正式形成。约翰·福布斯·纳什给出了纳什均衡的概念和均衡存在定理。博弈的参与者们在平等的对局中各自依据对方的策略变换自己的对抗策略，以达到利益最大化的目的。在博弈中，如果一个参与者寻求以一种可以最大化自己收益的方式进行博弈，那么这个参与者就是理性的。一般情况下，博弈的前提是认为所有的参与者都是理性的。

2.博弈论的基本要素(www.xing528.com)

博弈论的基本概念包括参与者、策略、收益、信息、均衡等。其中参与者、策略和收益是最基本要素。

（1）参与者：是博弈的主体，也是博弈中做出决策的行为者，每一个参与者都有一组可选择的策略，其通过选择策略或行动以最大化自己的收益水平。只有两个参与者的博弈称为“两人博弈”，而参与者多于两个的博弈称为“多人博弈”。

（2）策略：参与者在一局博弈中的策略是指在博弈各方所有可能的行动组合下完整的行动规划。策略决定了参与者在博弈的各个阶段所采取的行动。“策略”有时易于和概念“行动”混淆。参与者在博弈中某一点的动作称为行动，而策略是指在博弈的整个过程中策略所采取的动作集合。参与者的策略决定了其在博弈中的每一个阶段中，对方的每一不同的行动下如何动作。参与者所能采取的策略所组成的集合称为策略集。所有的参与者都只有有限个策略的博弈称之为“有限博弈”，否则称之为“无限博弈”。策略组合是每个参与者都完全选定他们在博弈中所有行动的一套策略。一个策略组合中，每个参与者都必须包括一个且只能一个的策略。

博弈策略可以分为纯策略与混合策略。纯策略：是指参与者在博弈中可以选择的行动方案。使用纯策略，参与者在任何一种情况下，只能选择一种特定行动。混合策略：如果允许参与者以某种概率随机选择不同的纯策略，则该策略称为混合策略。参与者在进行决策时根据纯策略空间上的这种概率分布在纯策略中随机选择加以实施。纯策略的数目是有限的，但是因为概率是连续的，所以混合策略可以有无限多个。每个纯策略都是一个“退化”的混合策略，即以概率1选择某一纯策略，以概率0选择其他纯策略。纯策略的收益可以用效用表示，而混合策略的收益则以期望效用来表示。

（3）收益：也称支付。对于由博弈中各参与者选择的策略组成的每一组可能的策略组合，博弈都会产生一个结果表示各博弈方在该策略组合下的得与失，即为各自的收益。收益常常是参与者策略的函数，其值可以为正也可以为负。

（4）信息：是指参与者的特征、支付函数、收益矩阵以及策略空间等，参与者可能知晓所有参与者的相关信息，也可能不完全知晓。

（5）博弈均衡：是指所有博弈参与者的最优策略或行动的组合。均衡状态是指所有的参与者都不想改变自己现有策略的一种相对静止的状态，一般称之为“纳什均衡”。纳什均衡是一种稳定状态的策略组合，在纳什均衡中，每个参与者的策略都是对其他参与者策略的最优反应。

3.博弈的类型

根据不同的依据，博弈可以有不同的分类。根据博弈参与者之间的关系，博弈可以分为合作博弈与非合作博弈。合作博弈和非合作博弈的区别主要在于博弈中的参与者之间在采取行动时需不需要遵循一个共同遵守的具有约束力的协议，如果需要，则他们之间的博弈就是合作博弈，否则，该博弈就是非合作博弈。合作博弈理论主要研究博弈的参与者们如何协作以均衡地分配他们合作所得到的收益，即主要研究收益的分配问题。而非合作博弈主要研究博弈的参与者们在所得收益相互影响的局势中如何选择策略以最大化自己的收益，也即策略选择问题。

根据博弈的参与者是否同时采取行动，博弈可以分为静态博弈和动态博弈。静态博弈：指在博弈中，博弈的参与者同时行动，选择各自的策略；或者参与者虽非同时行动，但是后行动的博弈方并不知道先行动的博弈方采取了什么行动。动态博弈：是指在博弈中，参与者的行动有先后顺序，并且后行动的博弈方能够观察到先行动的博弈方所选择的行动。按照博弈的参与者对其他博弈参与者的相关信息了解程度，博弈还可以被分为完全信息博弈和不完全信息博弈。完全信息博弈是指在博弈过程中，每一位博弈参与者对其他参与者的特征、策略空间及收益函数都完全了解。否则，该博弈就是不完全信息博弈。完全信息静态博弈，不完全信息静态博弈，完全信息动态博弈和不完全信息动态博弈这四种类型的博弈所对应的均衡概念分别为：纳什均衡、贝叶斯纳什均衡、子博弈精炼纳什均衡和精炼贝叶斯纳什均衡。

4.重复博弈

重复博弈（Repeated Game）是一类特殊的动态博弈。重复博弈是指相同结构的原博弈被重复多次，其中的每一次博弈都被称为“阶段博弈”。由于每一次博弈时，该阶段博弈之前的博弈都是可以观测到的，因此在重复博弈中，每个参与者在每个阶段博弈中所选择的策略都依赖于其他博弈参与者过去的行为，同时也必须考虑到自己当前阶段博弈所选择的行为对其他参与者未来的行为也会产生影响。如果博弈只进行一次，那么每个博弈的参与者就都只关心这个博弈的一次性的收益；如果博弈是多次重复的，那么，博弈的参与者则存在着当前短期的利益和以后多次重复博弈的长远利益的均衡。博弈方为了得到总的较高的收益，有可能会选择牺牲当前的利益，从而建立起一个好的声誉以换取长远的较高的总收益，因此，可能会选择不同于单次博弈的均衡策略。根据阶段博弈的重复次数，可以将重复博弈分为有限次的重复博弈和无限次的重复博弈。

对于有限次重复博弈，其总体得益可以用重复博弈的总得益或平均得益表示，并且可以用逆向归纳法求解。而在无限次重复博弈中，由于心理上的原因和实际得利的影响，博弈参与者通常更看重于近期利益，而对长期利益相对看轻，因此，不同期的得益对博弈参与人的决策有着不同的影响。参与者的总收益应为所有阶段博弈的收益的贴现值之和或加权平均数。

5.重复监听-转发博弈的随机最优反应均衡

传统博弈论中的纳什均衡认为，在有限重复博弈中，每一个博弈的参与者都完全理性，不受任何随机误差和认识偏差的干扰，并存在一种可以让每个博弈参与者选择的策略都是对其他博弈参与者选择的策略的最优反应均衡点，并且任何一个参与者都没有偏离该均衡点的动机。

然而人们在大量的实际博弈实验中发现，博弈参与者在博弈中并不一定能够足够理性并在博弈中选择纳什均衡，他们的实际选择常常偏离纳什均衡，并且这种对纳什均衡的偏离是系统性的。因而纳什均衡在实际环境中极易遭到违背，成为一种脆弱的博弈均衡。为了解决这个问题，行为博弈论（Behavioral Game Theory）被提出。行为博弈论将行为与传统博弈论相融合，通过大量的博弈实验，来观察理论推断与实际博弈结果之间的差异。行为博弈论认为博弈参与行为人在进行博弈决策时，获取信息的认知能力是有限的，因而也是很难完全理性的，因此他不能像完全理性假定的那样最大化其收益函数，从而不能采取其在完全理性状态下的最优策略。但是博弈的参与者在博弈的重复过程中会逐渐地掌握更多的信息，并不停地努力追求理性，最终仍会向传统的纳什均衡收敛。随机最优反应均衡（Quantal Response Equilibrium，简称QRE），也称量子反应均衡，是行为博弈论的一个重要概念，它基于有限理性并通过不停地修正博弈参与者的行动达到最后的均衡。

现有文献提出并研究了博弈的随机最优反应均衡QRE，并认为在实际环境中的各种实际选择与纳什均衡之间并不一致，参与者根据博弈中各种策略组合下的相对预期收益来进行选择。但在实际的有限认知能力的约束下，参与者可能会受到各种随机误差的干扰，从而无法正确预测各策略所能达到的预期收益。随机最优反应均衡假定，每个参与者都知道自己的策略选择和其他参与者的策略选择都会受到随机误差的干扰，但是各参与者仍能在这种状态下达到一个他们认为的彼此“最优反应”的均衡点。因此，量子反应均衡是一种“有限理性均衡”。QRE认为在实际的环境和情况中，博弈的参与者虽然“在信念上是理性的”，但并不能保证他是完全理性的。因而在计算每个博弈策略的预期收益时，参与者会不可避免地受到各种误差和认识偏差影响而出错。因此，在实际环境中的有限认知能力使得参与者无法选择传统的纳什均衡下的最优策略，而只能选择他当时认为的最好策略。在重复博弈的不断进行过程中，参与者会根据每一次的博弈结果不断地学习，提高自己的认知能力，并修正自己的看法。随着时间的推移，博弈的均衡点在重复博弈的每个阶段不断变动，并最终向纳什均衡收敛。

（三）分布式哈希存储理论基础

1.分布式哈希表

哈希，就是把任意长度的输入，通过哈希（散列）算法，变换成固定长度的输出，该输出就是哈希（散列）值。分布式哈希表（Distributed Hash Table，简称DHT）是一种分布式数据结构，是一张由一定范围内网络内的全体节点共同维护的哈希表。网络中的每个节点维护整张哈希表的一个片段，也即网络中的每个节点负责网络中一部分的路由信息，并存储网络中的一部分资源数据，从而实现整个DHT网络的资源存储和检索。

在DHT网络中，首先将每一份资源都用关键字进行标识，DHT系统对其中的每个关键字进行哈希，得到资源的关键字键值key。同样对网络中的每个节点ID进行哈希得到节点ID的键值value。资源关键字键值和节点ID键值都是唯一的。按照某种映射关系，将关键字键值映射到节点键值上，该节点键值对应的节点就存储此关键字键值的对应信息。所有的<key.value>构成一张巨大的信息索引哈希表。哈希表被分割成不连续的块，网络中的每个节点被分配给一个属于自己的哈希块，也即整张哈希表的一个片段。每个节点按照某种规则维护哈希表的一部分。

用户搜索资源时，用同样的哈希算法计算出每个搜索资源关键字的键值key，只要查询报纹路由到相应的节点，该节点维护的哈希表的片段中含有要查找的<key.value>对，则根据关键字键值可以知道其对应资源的存储位置，从而能够快速定位资源的位置。例如，节点A负责存储键值key为8000～8999的对象；而节点B负责key为7000～7999的对象。这样就可以将资源分布地存储在网络的节点中。根据对整张哈希表不同的分割规则，可将DHT分为不同的系统。在不同的系统中，每个节点要维护邻居节点也各不相同。

2.Chord协议

Chord是一种基于DHT的分布式查询协议。一个有N个节点的系统在稳定状态的时候，每个节点只需维护O（log2N）个其他节点的信息，查询操作也仅需要付出O（log2N）的搜索代价就能准确地定位到查询数据。在Chord网络中，节点也可以随时加入或者离开网络，这对在动态变化的大规模的分簇的无线传感器网络中分布式地存储簇头节点的声望值是比较合适的。

Chord使用一致性哈希作为哈希算法。在一致性哈希算法中，资源信息键值和节点ID键值处于同一值域。在将资源信息映射到节点时，使用资源信息的关键字和节点的ID进行一致性哈希运算并获得键值。根据键值存储内容时，资源信息将被存储到具有与其键值最接近的ID的节点上。例如键值为1001的内容，系统中有ID键值为1000，1110，1100的节点，该内容将被映射到1000节点。为了构建查询所需的路由，一致性哈希要求每个节点存储其后继节点（ID键值大于自身的节点中最小的）和前驱节点（ID）键值小于自身的节点中最大的位置信息（如IP地址）。当节点需要查找内容时，就可以根据内容的键值决定向后继（Successor）或前驱节点（Predecessor）发起查询请求。

收到查询请求的节点如果发现自己拥有被请求的目标，可以直接向发起查询请求的节点返回确认；如果发现不属于自身的范围，可以转发请求到自己的后继/前驱节点。为了维护上述路由信息，在节点加入/退出系统时，相邻的节点必须及时更新路由信息。这就要求节点不仅存储直接相连的前驱节点位置信息，还要知道一定深度的间接前驱节点信息，并且动态地维护节点列表。当节点退出系统时，它的后继节点将尝试直接连接到最近的前驱节点，连接成功后，从新的前驱节点获得前驱节点列表并更新自身的节点列表。同样的，当新的节点加入系统中时，首先根据自身的ID键值找到前驱节点。

为了提高查找效率，在Chord协议中，每个节点负责的不再是直接相邻的节点，而是键值间距为2i的节点序列（i=1，2，...，N）。如都为160位的二进制整数。在有N个节点的网络中，Chord中的每个节点只需要维护O（log2N）个节点的资源信息，这些信息的集合被称为查询表（Finger Table）。每次搜索也只需要付出O（log2N）次的代价就能定位到所需查询的资源数据。在查询的过程中，查询节点将请求发送到节点ID键值与资源键值最接近的节点上。收到查询请求的节点如果发现自身存储了被查询的信息，则直接回应查询节点；如果被查询的信息不在节点自身，则根据查询表Finger Table将请求转发到与查询资源键值最接近的节点上。这样的过程一直持续到找到相应的存储节点为止。该查询过程实际上就是折半查找的过程。跟顺序存储的一致性哈希比较，Chord协议中查询需要的跳数由O（N）减少到O（log2N）。这样即使在具有N＝10000000个簇的大规模无线传感器网络中，查询的跳数也仅为7，每个簇头节点仅需存储24个其他簇头节点的信息。考虑到节点的加入和离开的情况，Chord系统中节点之间传递的消息也不会不超过O（log2N）个。