Abstract: In most routing algorithms of the previous work, the flooding method is used to obtain auxiliary information, which wastes network resources. Motivated by this, a distributed social distance routing algorithm was proposed. Firstly, the stability and regularity of contact between nodes were analyzed to determine the friend relationship. Then, the social-distance between nodes was constructed by the friend relationship. In addition, a table for recording the shortest social distance to other nodes was maintained by each node, and the minimum social distance was continually updated by exchanging and comparing the information in the table. The construction of social distance only needs to exchange information among friends instead of all nodes, which can greatly reduce the time of auxiliary-information exchange. Finally, when the packet was sent to the relay node with a smaller social distance to its destination node, the delivery ratio could be significantly improved. The experimental results demonstrate that, compared with the Probabilistic Routing Protocol using History of Encounters and Transitivity (PRoPHET) algorithm, the delivery ratio of the proposed algorithm is increased by about 3%, the data packet transmission delay is reduced by about 27%, and the auxiliary-information exchange times is reduced by about 63%. Compared with the routing based on Betweenness centrality and Similarity (SimBet) algorithm, the delivery ratio of the proposed algorithm is increased by about 11%, the data packet transmission delay basically equals, the auxiliary-information exchange times is reduced by about 63%. The social distance algorithm provides a theoretic support for large-scale mobile opportunistic networks, because of its better performance in scalability.

Key words: mobile opportunistic network, routing protocol, friend relationship, auxiliary-information, social distance

摘要： 目前大部分机会路由算法采取洪泛的方式进行辅助信息的交换造成网络资源浪费严重。针对此问题，提出了一种分布式社会距离路由算法。首先，通过分析节点间接触的稳定性与规律性来确定朋友关系。其次，通过朋友关系来构建节点间的社会距离；进一步地，每个节点维护一张用于记录当前已知的到其他节点的最短社会距离表，通过朋友节点之间相互交换并比较表中信息来不断更新最短社会距离。由于社会距离的构建与更新只需要朋友之间交换信息而并不需要全部节点来参与，极大地减少了辅助信息的交换次数。最后，数据包被发送到与其目的节点社会距离较近的中继节点，保证了数据包高效率地投递。实验结果表明：与接触和传输记录的概率路由（PRoPHET）算法相比投递率提升约3%，包传输延时降低约27%，辅助信息交换次数减少约63%；与基于中心度与相似度的路由（SimBet）算法相比包投递率提升约11%，包传输延时方面基本持平，辅助信息交换次数减少约63%。社会距离路由算法在可扩展性方面的良好表现，为移动机会网络大规模部署提供了理论支撑。

关键词: 移动机会网络, 路由协议, 朋友关系, 辅助信息, 社会距离