Abstract: At present, routing algorithms based on community for the opportunistic network are on the base of static social relations, community is seen as steady state. But in practice, due to the mobility of opportunistic network nodes, the social relation topology dynamically evolutes with time, community division based on static social relations will cause the problems of message low delivery rate and large transmission delay, etc. In order to solve the problem of inaccurate social relationship, this paper studies the social relations topology dynamic evolution of the opportunistic network, proposes a prediction model based on Markov chain for the social relations of the opportunistic network. First of all, dividing run time of the opportunistic network into time slices of equal length, then constructing social relations at each time slice; secondly, decomposing the social relations of the network into the social relations between the nodes; constituting a state sequence for the social relations between the nodes; finally, according to the meeting status sequence sample data of node pairs based on time slice sequence, establishing the meeting state transition probability model for the node pairs. The experimental results show that in the social relations of the time sensitive opportunistic network, the evolution model based on Markov chain proposed in this paper can predict the changes of topology, the accurate rate reaches above 80%.

Key words: opportunistic networks, time sensitive, social relation topology evolution, Markov model

摘要： 目前基于社团的机会网络路由算法都是以静态社会关系为依据，社团呈现为静态。但实际中，机会网络节点的移动性使得网络社会关系拓扑随时间动态演化，社团也随之变化，以静态社会关系拓扑为依据的社团划分会带来消息投递成功率低，传输延迟大等问题。为了解决静态社会关系拓扑下社团时间不敏感的问题，研究了机会网络上社会关系拓扑时间敏感的动态演化，提出了一种基于马尔可夫链的机会网络社会关系拓扑预测模型。将机会网络运行时间划分为等长的时间片，在每个时间片内构建网络社会关系拓扑，并将社会关系拓扑分解为节点对之间的社会关系，使得对社会关系拓扑的分析化简为对节点对之间的社会关系的分析；由节点对在时间片序列中的相遇状态构成节点对社会关系状态序列，根据基于时间片序列的节点对相遇状态序列样本数据，建立了节点对相遇状态转移概率模型。实验结果表明，在时间敏感的机会网络社会关系中，该基于马尔可夫链的演化模型能够预测拓扑变化，准确率达到80%以上。

关键词: 机会网络, 时间敏感, 社会关系拓扑演化, 马尔可夫模型