金小俊，吴 军，薛冒杰，白光伟

(南京工业大学 计算机科学与技术学院，江苏 南京 211816)

0 引 言

随着移动设备(如手机、PDA等)的大量普及，通过设备的移动带来机会式连接从而搭建起临时网络，使得在不具备通信基础设施的网络环境中设备间通信成为可能，这种具备移动特性和社会性的新型网络形式称为移动社会网络[1](mobile social networks，MSN)。由于人们之间社会关系相当稳定且存在一定的依赖性，网络中会出现簇聚现象，节点以自组织的方式形成族，族内的节点联系紧密且处于相对稳定状态，因此通过蚁群算法可以有效设计分布式且自适应性的路由算法。在移动网络的环境中，节点的自私性体现为节点对消息的转发意愿的强弱，节点的转发意愿的强弱与节点间的社会关系强度有关[2]。社会关系越强，节点的转发意愿就越强，相应的消息转发效益就越大，因此消息发送节点在消息传输过程中会选择社会关系更亲密且传输意愿更高的节点作为中继节点。但由于移动智能设备的资源受限且联络广泛，节点容易受网络中不可信自私节点的影响。网络中自私节点会表现出惰性自私，中继节点与消息发送节点的社会关系亲密但不愿意参与消息的转发甚至恶意丢包，导致整个网络消息传输性能的降低，造成网络消息传输的不可信。如何利用蚁群算法特性的同时有效解决网络中自私节点惰性传输问题以提高消息传输可信性，并利用节点的社会关系选择传输意愿高的中继节点，成为设计可信移动社会网络路由算法的关键问题。

1 相关工作

1.1 蚁群算法

蚁群优化算法(ACO)是意大利学者Dorigo M等[3]提出的分布式智能模拟算法。蚂蚁在觅食过程时随机搜索自身周围的环境，并在所经过的路径上留下具有信息传递作用的信息素以指导其它蚂蚁进行路径选择。在搜索路径过程中某条路径长度越短，蚂蚁在该路径来回次数越多，因此较短路径上的信息素含量就越高，最终所有蚂蚁寻找食物的路径会收敛到较短的路径上。这种蚁群协作行为便表现出一种信息正反馈现象，即某一路径长度越短，则其它蚂蚁选择该路径的概率越大[4]。

文献[5]中提出的改进蚁群算法在原有蚁群算法的基础上引入了位置带概念并使用抵抗素策略达到能量均衡，但该算法对路由性能的提升有限。文献[6]提出了一种多目标蚁群优化算法，该算法通过最小化传输距离、传输延时和方向且最大化进展和生存时间构造移动概率函数，选择移动概率最大的节点作为最佳下一跳节点，但忽略了节点的移动性和社会属性。文献[7]提出了兼顾能量平衡和拥塞控制的蚁群优化路由算法，该算法，选择具有最大剩余能量、最小路径花费和最小时延变化的最优节点构建路由，同时限制能量不满足条件的节点或者路径传输数据，但该算法只考虑到节点的能量消耗，不能避免自私节点对网络的影响。文献[8]提出了基于蚁群智能的MSN路由算法，通过节点对间的消息列表为其它节点发送消息时选择合适的中继节点提供有效信息，但该算法只考虑到路径最短和节点交互次数，没有考虑到节点间路径的可信。

1.2 可信机会路由

机会网络[9]是一种不需要源节点和目标节点之间存在完整链路，通过节点随机移动带来的相遇实现节点通信的自组织网络。MSN网络[10]是具备社会属性的机会网络，其节点主要是人类使用的移动设备，节点之间的通信依靠节点协同合作的网络。文献[11]提出网络中自私节点对路由传输的影响体现在传输成功率、传输延迟和网络开销，中继节点的自私行为会导致网络中消息传输性能的降低。文献[12]提出了可信概念，可信表示网络节点的行为及其结果是可以预测的，利用节点的可信解决网络中自私节点不参与网络合作转发及恶意节点丢包行为的问题。文献[13]提出一种基于蚁群算法的节点可信安全路由协议，将节点信任评估模型引入到蚁群路由算法中，提高无线传感器网络的节点可信度，以节点可信度为依据隔离惰性节点，增强网络安全性，但其迭代算法复杂度高，对节点资源消耗较大。文献[14]提出了动态信任信息聚合算法，该算法利用反馈信任值聚合方法进行探索，然后基于蚁群算法通过多次循环寻找出多条较优的独立信任路径,并获得最终的反馈信任值，该算法计算周期长，无法适应网络拓扑的快速变化。文献[15]提出了基于社会自私性的路由算法，消息在转发过程中要考虑到节点的社会属性和传输消息的优先级以提高消息传输效率，但该算法没有考虑到节点的自私行为。

2 可信邻居节点集的构建

本文基于社会网络分析理论描述移动社会网络模型和网络节点的社会特征。假设网络节点同属于一个族内，节点状态相对稳定。用图G=(V,E) 表示一个包含n个节点的MSN，V={V1,V2,…,Vn}(n≥1) 表示网络中移动节点的集合， ∀Vi∈V，Vi表示网络中第i个移动节点，E为节点间边e的集合。本文使用二元组 〈Tij,Iij〉 表示消息发送节点i对邻居节点j的综合信任值评估和社会亲密度评估。

定义1 因节点社会自私性导致丢包行为的节点为惰性自私节点，即自私节点。

定义2 与节点进行正常消息交互且没有自私行为的节点为可信节点。

2.1 综合信任值

综合信任值Tij是根据节点间的历史交互信息和公共相遇节点的推荐信息进行的信任值评估，可以有效分析判断节点的可信状态。通过节点的综合信任值评估可以隔离自私节点参与到消息转发过程中，保证网络消息转发选择可信的中继节点，避免自私节点的惰性传输。

(1)直接信任值

基于TMS[16]中提出的信任模型，网络节点间的信任值评估服从Beta分布，即Beta(α,β)， 其中αij和βij分别表示节点i与节点j成功交互消息的次数和失败的次数。但在实际情况中，Beta分布可能无法准确反映真实的转发行为，例如由于链路的丢失带来消息的转发失败。因此，在评估节点信任值的时候应当考虑消息转发的不确定性。为了解决这个问题，本文采用了文献[17]提出的方法，利用D-S理论来量化消息传输过程中的不确定性，将节点i与节点j之间的交互分为成功交互Sij、 失败交互Fij和不确定交互Uij， 其计算公式为

(1)

(2)

(3)

(4)

其中，θ是不确定交互中实际成功交互的占比，默认值为0.5[18]。

(2)间接信任值

定义4 节点i与节点j对公共相遇节点直接信任值的相似程度称为信任相似度cos(i,j)。

节点i为节点j的邻居节点，节点i与节点j相交集的公共相遇节点集为Ns， 信任相似度cos(i,j) 的公式为

(5)

其中，Ns={N1,N2,…,Nn} 表示公共相遇节点集，采用信任向量表示节点i对所有公共相遇节点的直接信任评估，其表达式为：Tis=[TiN1,TiN2,…,TiNp,…,TiNn]，TiNp(Np∈Ns,1≤p≤n) 表示在节点i的公共相遇节点集中节点Np的直接信任值。

(6)

(3)综合信任值

(7)

(4)综合信任值的更新

(8)

其中，ρT是信任值时间衰减系数。综合信任值时间衰减系数ρT取值为0.8。

2.2 构建可信邻居节点集

消息发送节点通过定期发送Hello报文给通信范围内的中继节点，中继节点在收到消息发送节点发送的Hello报文后会立刻回应ACK报文，消息发送节点将发送ACK报文的中继节点构建为邻居节点集Nv。 蚁群算法通常会将消息发送节点通信范围之内的邻居节点集Nv都纳入到蚂蚁探索的节点候选集中，但邻居节点集Nv中可能会存在自私节点，通过对路由节点进行信任评估确定中继节点的可信状态，以有效规避自私节点惰性传输对消息传输的影响，增强网络传输的可信性。依据得到的消息发送节点i对中继节点j的综合信任值，对中继节点j进行判别：

(1)0

(2)Y≤Tij≤1，表示节点j是可信节点，节点j直接进入节点i的可信邻居节点集Ni。

其中，Y表示可信阈值，Ni为节点i的可信邻居节点集。根据实验仿真可知，可信阈值Y取值为0.6。

3 蚂蚁启发函数的改进

3.1 社会亲密度

移动社会网络的主要载体是人，因此节点移动过程中带有人类社会关系特征。在MSN网络中，节点的自私性表现为中继节点是否愿意转发消息，而中继节点的转发意愿强度取决于节点间的社会关系强度，即节点间的消息交互是否频繁。

定义7 节点i与节点j间社会关系强度的度量称为社会亲密度Iij。

社会亲密度Iij反映了网络局部拓扑情况，将消息转发给社会关系紧密、频繁接触的节点更容易建立稳定的消息传递链路。社会亲密度Iij的值越大，说明节点i和节点j之间的关系越紧密，中继节点传输意愿更积极，传输消息的可靠性越高；反之说明节点i与节点j之间的关系越疏远，传输消息的可靠性越低。设Cij为节点i向节点j转发的消息次数，即节点i到节点j的出度值。社会亲密度Iij计算公式为

(9)

(10)

(11)

3.2 构建启发函数

蚁群算法中的启发素具有局部性，配合具有全局性的信息素，使得转发决策更高效。但传统的启发函数仅考虑到节点间的距离，将节点间距离作为唯一的启发式因子，无法引导消息传输给传输意愿更高的节点。本算法在原启发函数的基础上增加了社会亲密度，通过节点间的社会关系构建新的启发函数，在充分利用传输意愿高且传输可信中继节点基础上，提高节点中继传输的可靠性。启发函数计算公式为

(12)

其中，Iij表示节点i评估节点j社会亲密度，dij表示节点i和节点j的空间距离。

通过将反映节点间社会关系强度的社会亲密度引入到启发函数中，可引导节点将消息转发给关系更紧密、消息交互更频繁的中继节点，增加了网络传输的可靠性。

4 Trust-ACO算法的提出

传统蚁群算法通过蚂蚁在其所经过路径上留下的信息素进行路由选择，但其不能应对MSN网络中节点社会自私性导致的消息传输问题。Trust-ACO算法在传统蚁群算法基础上进行了算法改进，通过综合信任值构建消息发送节点可信邻居节点集，避免惰性自私节点参与到消息传输中以提高消息传输的可信性；引用社会亲密度改进启发函数，将消息转发给传输距离近且社会关系紧密、传输意愿积极的中继节点提高消息传输性能。

4.1 状态转移概率函数

消息发送节点在进行消息传输时，如果目的节点在其邻居节点集Nv中，则直接转发给目的节点，并更新相应的链路信息。如果目的节点不在其邻居节点集Nv范围内，则查看可信邻居节点集Ni并按照状态转移概率函数来确定下一跳中继节点。状态转移概率函数由信息素和启发函数综合决定，根据文献[20]其计算公式为

(13)

其中，Ni为消息发送节点i通过综合信任值构建的可信邻居节点集，τij为消息发送节点i到中继节点j的信息素值，ηij为消息发送节点i到中继节点j基于社会关系强度的启发函数值；参数α与β分别为信息素τij和启发值ηij的权重。

4.2 蚂蚁信息素含量更新

蚁群每次迭代完成后，会对蚂蚁发现的路径进行路径质量评估，并对本次迭代中的路径进行信息素含量更新。蚂蚁路径质量计算公式为

(14)

其中，A=0.5[21]是一个预设值常量，Iij表示消息发送节点i评估中继节点j的社会亲密度，dij表示消息发送节点i与中继节点j之间的距离。路径质量评估是基于节点间的社会亲密度，社会亲密度越高，节点间消息传输意愿越积极，那么节点间的路径质量也越高。信息素的更新公式为

(15)

4.3 消息转发策略

(1)若目的节点在邻居节点集中，则将消息发送给目的节点，并更新相关信息；

(2)若消息发送节点不在目的节点的邻居节点中，则该节点根据式(8)计算当前邻居节点综合信任值决定邻居节点是否加入可信邻居节点集Ni， 对可信邻居节点按式(13)中的状态转移概率函数选择下一跳中继节点；若可信邻居节点集Ni中没有可信节点，则不进行消息转发，将消息保留在本节点中；

(3)重复以上过程直到消息到达目的节点或者超时被丢弃为止。

算法主要流程如图1所示。

图1 算法流程

算法的伪代码如下：

算法： 族内可信蚁群机会路由改进算法(Trust-ACO)

Input： 网络中所有节点

Output： 下一跳节点

Begin

节点i接收消息(destd) //消息目的节点为节点d

节点i发送Hello报文，构建邻居节点集Nv

If(d∈Nv) //目的节点d在邻居节点集Nv中

节点i发送消息

Else //目的节点d不在邻居节点集Nv中

节点i计算邻居节点集Nv中所有节点的综合信任值T

For (j=0;j

If(Y≤Tij≤1)

jjoinNi//节点j加入节点i的可信邻居节点集Ni

Else

dropj//节点j不加入节点i的可信邻居节点集Ni

If(Ni≠∅) //可信邻居节点集Ni中存在可信节点

If(NUM(Ni)>1) //可信邻居节点集Ni中有一个以上可信节点

For (j=0;j

计算节点i的蚂蚁启发函数ηij

计算节点i的状态转移函数Pij

按Pij选择下一跳节点， 转发消息

评估蚂蚁路径质量Qij， 更新蚂蚁信息素

Else //可信邻居节点集Ni中只有一个可信节点

节点i转发消息

评估蚂蚁路径质量Qij， 更新蚂蚁信息素

Else //可信邻居节点集Ni中没有可信节点

节点i保留消息

Return 下一跳节点

End

5 仿真实验

本文利用ONE仿真软件作为实验模拟平台来实现Trust-ACO算法，并对其性能进行验证。本文将Trust-ACO算法与Epidemic、PROPHET、ACO(ant colony optimization)算法进行比较。Epidemic算法在两个节点相遇时交换对方缓存队列中的消息ID，交换对方携带而自己没有携带的消息。PROPHET算法是一种基于节点接触概率的路由算法，当两个节点相遇时，它们的接触概率增加，否则随时间衰退。ACO算法是一种基于蚁群算法优化的网络路由算法，通过探测消息发送节点与中继节点间的距离大小和路径上的信息素引导消息传输给下一跳节点。

5.1 仿真环境

实验采用ONE模拟器中MIT Reality[22]数据集一个月中连续工作日的相遇数据，该数据集对随机抽取的97名MIT的学生和教职工进行了数据采样，采样时间为246天，共记录了110多次彼此间的相遇机会。MIT Reality数据集将移动基站信息作为用户的位置轨迹数据，同时还包含了用户的社会关系属性。数据集由于受节点间社会关系及节点个体自私趋利等因素的影响，适用于本文的研究背景。本文使用其数据集中240 min内移动轨迹作为实验中节点的移动轨迹。具体设置见表1。

表1 实验仿真参数设置

网络性能评估主要为传输成功率和消息传输时延。传输成功率为发送成功的消息数与产生的总消息数的比值，表征了算法的传输可靠性；消息传输时延为消息从源节点转发到目的节点的平均消耗时间，指标评估路由算法的延迟性。

5.2 实验结果与分析

本实验通过分析不同消息生存时间、网络中自私节点数和对社会亲密度的情况下算法的性能，并与其它算法在相同环境下进行性能对比，分析本算法性能优劣。

如图2所示，仿真显示Trust-ACO算法随着可信阈值增加其传输成功率的变化情况。随着可信阈值的增加，传输成功率先增加后减少。在低可信阈值时，存在自私行为的中继节点被判定为可信节点加入到消息传输过程中，该节点因社会自私性存在的丢包行为影响了网络中消息的传输成功率；在高可信阈值时，网络中可信的中继节点数量减少，消息无法有效转发到目标节点，导致传输成功率下降。从实验仿真图可以看到可信阈值在区间[0.5,0.7]时，有较好的传输成功率，因此可信阈值取0.6时，网络性能最佳。

图2 不同可信誉值时算法性能对比

如图3所示，仿真显示4种路由算法随着消息生存周期的增加其性能指标的变化情况。随着消息生存周期的增加，Epidemic和PROPHET算法传输率随时间缓慢提升，因为这两种算法采用了无限副本转发策略，消息生存周期的增加会让网络存在大量的消息，导致节点缓存中没有及时转发的消息被删除从而降低了传输率。而Trust-ACO算法由于考虑了综合信任值和社会亲密度在传输成功率方面有一定程度的提升，在消息生存时间达到120 min后其传输成功率达到60%且继续增加。ACO算法随着消息生存周期的增加消息转发成功率最低。在消息传输时延方面Trust-ACO算法相对于其它算法比较小。

如图4所示，在网络中设置一定数量的自私节点，显示4种路由算法随着自私节点数量的增加其性能指标的变化情况。当自私节点数量的增加时，4种路由算法的传输成功率都有一定下降。Trust-ACO算法在性能方面较优越，当自私节点数不超过20时传输成功率在80%以上；当网络中自私节点数量为40时传输成功率为69%。Epidemic和PROPHET算法因无法抑制节点的自私行为，消息传输成功率下降明显。ACO算法由于没有采用避免自私节点的路由策略，节点自私行为对其影响较大。

如图5所示，设置不同的消息发送间隔时间，显示4种路由算法性能的变化情况。在网络中节点产生消息越多，节点间消息交互越频繁，则节点间社会关系越亲密，即消息产生间隔时间越短，节点社会亲密度越高。随着消息产生间隔时间的增加，Epidemic和PROPHET算法的传输成功率和消息传输时延没有明显的变化。由于Trust-ACO算法考虑到节点间的社会亲密度，表现出一定程度上的性能优势，在消息产生间隔时间为5 min时，由于节点间频繁的消息传输，其节点间社会亲密度变高，消息的传输成功率为85%，且随着间隔时间增加，消息传输成功率呈下降趋势。ACO算法由于没有考虑社会属性，消息传输率保持60%左右。在消息传输时延方面，Trust-ACO算法在消息产生间隔时间低于20 min时优于其它算法。

图3 不同消息生存周期时算法性能对比

图4 不同自私节点数量时算法性能对比

图5 不同消息产生间隔时间时算法性能对比

如图6所示，显示设值不同的消息周期数，可信节点和自私节点的综合信任值变化情况。可信节点的平均综合信任值随着周期的增加呈上升趋势且最后接近于1；而自私节点的平均综合信任值随着周期增加呈下降趋势且最后接近于0.1，表明综合信任值可有效区分出网络中的可信节点和自私节点。

图6 节点综合信任值随周期变化情况

6 结束语

本文通过分析移动社会网络的特征，提出了一种族内基于可信蚁群算法的路由算法。该算法利用蚁群算法分布式、自适应的特性在网络中寻找最优路径，首先利用节点间的历史交互信息评估节点综合信任值以有效选择网络中的可信邻居节点，然后基于社会亲密度的状态转移函数选择转发意愿更高、关系更紧密的中继节点进行消息的传输，最后实现族内的可信消息转发策略。然而，MSN网络中移动设备自身能量和缓存资源有限且计算资源较弱，算法如何在节点资源受限时依然有较优的传输成功率和传输时延，是进一步研究重点。