Progressive or Conservative: Rationally Allocate Cooperative Work in Mobile Social Networks

摘要

There are plenty of idle computational resources on the Internet, which could potentially be used for accomplishing huge tasks. More and more applications are being designed for exploring those idle resources. In this paper, we focus on the idle computational resources, including both human intelligence and machine computing abilities, in mobile social networks (MSNs). Based on the unique features of MSN, we design a new cooperative system, called social-crowdsourcing. The distributed and infrastructure-free features of the system make it more attractive than traditional crowdsourcing platforms. In the proposed system, a huge work is gradually partitioned into smaller pieces, and is propagated from node to node. However, how to partition and allocate these segments is a critical problem, which directly affects the work’s completion time and system throughput. Due to the lack of global information, independent relay nodes are likely to make conflicted decisions, which will cause an unbalanced workload distribution on participating nodes. In this paper, we find that, for a work at different processing stages, one should adopt distinct workload exchanging schemes, moving from a progressive method to a conservative one. Based on this observation, we propose an adaptive workload allocation scheme, in which a participating node can gradually switch his decision strategy according to the workload statuses of neighboring nodes. By using our approach, system throughput can be significantly improved, and large works can finish within a nearly optimal time. Unlike in traditional scheduling problems, we take a human’s rejection, contact delay, and social similarity into consideration. Extensive simulation results show that our proposed algorithms can successfully make full use of the idle resources in MSNs.