Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete
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. Particula...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | บทความวารสาร |
| Language: | English |
| Published: |
Science Faculty of Chiang Mai University
2019
|
| Online Access: | http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=7378 http://cmuir.cmu.ac.th/jspui/handle/6653943832/63814 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chiang Mai University |
| Language: | English |
| Summary: | 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. |
|---|