Paper Info
Title
Collaborative and Distributed Search System with Mobile Devices
Abstract
With the advances of communications, computing, and positioning technologies, mobile devices have been regarded as mobile computing platforms for various kinds of location-based and human-computation services. However, most existing applications regard each device as a sensor or focus on services with the computation on a single device. In contrast, this paper leverages a group of mobile devices as a collaborative and distributed search platform. Specifically, we propose a search system with mobile devices for rescue and patrol operations. The system utilizes mobile devices to find and assign the search route to each searcher in a collaborative and distributed manner. Given the roads to be searched in an area and the candidate start locations, our system minimizes the time required to search the whole area and guarantees that each road will be searched at least once. We first formulate the k-Person Search Problem for k mobile devices and prove that the problem is NP-Hard. To find the optimal solutions, we propose a centralized algorithm for a special case and an Integer Linear Programming formulation for general cases. We also devise an approximation algorithm. The algorithms can be used to dispatch the searchers before the operation starts. Moreover, to support online adaptation, we formulate the Path Refinement Problem for path exchange among searchers and propose a distributed algorithm to adaptively adjust the paths after the search starts. We also implement the proposed algorithms in mobile devices as a collaborative and distributed search system and demonstrate the efficiency of our algorithms with computation simulations and field trials.
Year
DOI
Venue
2012
10.1109/TMC.2011.173
Mobile Computing, IEEE Transactions
Keywords
Field
DocType
approximation theory,computational complexity,distributed algorithms,emergency services,groupware,integer programming,linear programming,mobile computing,search problems,NP-Hard,centralized algorithm,collaborative system,distributed search system,human-computation services,integer linear programming formulation,k mobile devices,k-person search problem,location-based services,mobile computing platforms,path refinement problem,patrol operations,positioning technologies,rescue operations,sensor,Mobile applications,algorithm/protocol design and analysis.,distributed applications
Mobile computing,Approximation algorithm,Mobile search,Algorithm design,Computer science,Computer network,Mobile device,Distributed algorithm,Search problem,Mobile telephony,Distributed computing
Journal
Volume
Issue
ISSN
11
10
1536-1233
Citations 
PageRank 
References 
2
0.39
17
Authors
3
Name
Order
Citations
PageRank
Chih-Ya Shen110317.13
De-Nian Yang258666.66
Ming Chen365071277.71