Paper Type |
Contributed Paper |
Title |
Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete |
Author |
Pattama Longani [a], Nopadon Juneam [b], Sanpawat Kantabutra*[c] |
Email |
sanpawat@alumni.tufts |
Abstract: In this article we consider a mobility model M = (S, D, U, L, R, V, C, O), where S is a set of sources, D a set of directions, U a set of users, L a set of user movements, R a set of source movements, V a set of velocities of sources, C a set of source coverages, and o a set of obstacles. Particularly, we study a problem called Multi-Sources Simultaneous Communication Problem (MSSCP) in this model. This problem is stated as follows: given a mobility model M = (S, D, U, L, R, V, C, O), k pairs of distinct sources {s1, s'1}, {s2, s'2},..., {sk, s'k}, and a time t e N, can all k pairs of sources simultaneously communicate throughout the duration t of the model without sharing a source? We show that the complexity of this problem is at least as hard as the One-In-Three 3-Satisfiability unless P=NP. In addition, we also give an exact algorithm and a heuristic one for MSSCP and show that if the communication among sources in MSSCP can be represented by a complete bipartite graph, Km,n, then MSSCP can be solved in polynomial time.
|
|
Start & End Page |
1205 - 1221 |
Received Date |
2015-05-20 |
Revised Date |
|
Accepted Date |
2016-03-28 |
Full Text |
Download |
Keyword |
wireless mobility networks, NP-completeness, intractability, bipartite |
Volume |
Vol.43 No.5 (OCTOBER 2016) |
DOI |
|
Citation |
Longani P., Juneam N. and Kantabutra S., Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete, Chiang Mai J. Sci., 2016; 43(5): 1205-1221. |
SDGs |
|
View:538 Download:148 |