Message Duplication Reduction in Dense Mobile Social Networks
Ken‐ichi Kawarabayashi, Fawad Nazir, Helmut Prendinger · 2010
In this paper we study the problem of message duplication in dissemination of dynamic content such as news or traffic information over a Dense Mobile Social Network (MSN). In MSNs mobile devices disseminate content only to the nodes whose subscribed interest match it. MSNs are used to improve the coverage and increase capacity as we assume that people in an intermittently connected MSNs are socially-related and tend to co-locate quite regularly. MSNs are similar to Disruption Tolerant Networks (DTNs) expect that in MSNs the assumption is that individuals follow predictable working day movement model and the users exchange profile and disseminate content only to the users in their social network. The analysis of three independent experiments conducted, shows that the current message forwarding protocols for dense MSNs can experience up-to 94% of duplicate messages in the worst-case because the messages are replicated to be routed over multiple delivery paths in-order to optimize the probability of successful message delivery. Although these approaches do (statistically) guarantee delivery probability but impose overheads on bandwidth, energy and memory. Therefore, in this paper we propose a message duplication reduction algorithm by exploiting the mobility predictability property of the users in MSNs. We model our problem as an on-line graph and solve the problem of message duplication by an algorithm on the well-known spanning tree problem. Furthermore, we divide our problem into three optimization problems and priorities them as minimize message delivery time, minimize message duplication and minimize message storage space. The study presented in this paper achieve message duplication reduction of 71.8% in the best-case (i.e. domination set of most influential users and many to many data delivery) and 14.8% in the worst case (i.e. selecting random users and one to one data delivery) while guaranteeing a given delay or delivery probability and lowering system wide traffic flooding.