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 |
id |
th-cmuir.6653943832-63814 |
---|---|
record_format |
dspace |
spelling |
th-cmuir.6653943832-638142019-05-07T09:57:20Z Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete Pattama Longani Nopadon Juneam Sanpawat Kantabutra 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. 2019-05-07T09:57:20Z 2019-05-07T09:57:20Z 2016 บทความวารสาร 0125-2526 http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=7378 http://cmuir.cmu.ac.th/jspui/handle/6653943832/63814 Eng Science Faculty of Chiang Mai University |
institution |
Chiang Mai University |
building |
Chiang Mai University Library |
country |
Thailand |
collection |
CMU Intellectual Repository |
language |
English |
description |
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. |
format |
บทความวารสาร |
author |
Pattama Longani Nopadon Juneam Sanpawat Kantabutra |
spellingShingle |
Pattama Longani Nopadon Juneam Sanpawat Kantabutra Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete |
author_facet |
Pattama Longani Nopadon Juneam Sanpawat Kantabutra |
author_sort |
Pattama Longani |
title |
Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete |
title_short |
Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete |
title_full |
Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete |
title_fullStr |
Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete |
title_full_unstemmed |
Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete |
title_sort |
multi-sources silmultanieous communication in the wireless mobility model is np-complete |
publisher |
Science Faculty of Chiang Mai University |
publishDate |
2019 |
url |
http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=7378 http://cmuir.cmu.ac.th/jspui/handle/6653943832/63814 |
_version_ |
1681425965268336640 |