File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Exact algorithms to minimize interference in wireless sensor networks

TitleExact algorithms to minimize interference in wireless sensor networks
Authors
Issue Date2011
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2011, v. 412 n. 50, p. 6913-6925 How to Cite?
AbstractFinding a low-interference connected topology is a fundamental problem in wireless sensor networks (WSNs). The problem of reducing interference through adjusting the nodes' transmission radii in a connected network is one of the most well-known open algorithmic problems in wireless sensor network optimization. In this paper, we study minimization of the average interference and the maximum interference for the highway model, where all the nodes are arbitrarily distributed on a line. First, we prove that there is always an optimal topology with minimum interference that is planar. Then, two exact algorithms are proposed. The first one is an exact algorithm to minimize the average interference in polynomial time, O(n 3Δ), where n is the number of nodes and Δ is the maximum node degree. The second one is an exact algorithm to minimize the maximum interference in sub-exponential time, O(n 3ΔO (k)), where k=O(√Δ) is the minimum maximum interference. All the optimal topologies constructed are planar. © 2011 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152474
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
Funding AgencyGrant Number
National Basic Research Program of China2007CB807900
2007CB807901
National Natural Science Foundation of China61103186
61073174
61033001
61061130540
Hi-Tech research and Development Program of China2006AA10Z216
Hong Kong RGC-GRF714009E
714311
HKU21476015
Funding Information:

The authors would like to thank Dr. Xiaoming Sun, Dr. Thomas Moscibroda and Dr. Yongcai Wang for helpful discussions. The research was supported in part by the National Basic Research Program of China Grant 2007CB807900, 2007CB807901, the National Natural Science Foundation of China Grant 61103186, 61073174, 61033001, 61061130540, and the Hi-Tech research and Development Program of China Grant 2006AA10Z216, Hong Kong RGC-GRF grants 714009E and 714311, and HKU Small Project Funding 21476015.

References

 

DC FieldValueLanguage
dc.contributor.authorTan, Hen_US
dc.contributor.authorLou, Ten_US
dc.contributor.authorWang, Yen_US
dc.contributor.authorHua, QSen_US
dc.contributor.authorLau, FCMen_US
dc.date.accessioned2012-06-26T06:39:29Z-
dc.date.available2012-06-26T06:39:29Z-
dc.date.issued2011en_US
dc.identifier.citationTheoretical Computer Science, 2011, v. 412 n. 50, p. 6913-6925en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/152474-
dc.description.abstractFinding a low-interference connected topology is a fundamental problem in wireless sensor networks (WSNs). The problem of reducing interference through adjusting the nodes' transmission radii in a connected network is one of the most well-known open algorithmic problems in wireless sensor network optimization. In this paper, we study minimization of the average interference and the maximum interference for the highway model, where all the nodes are arbitrarily distributed on a line. First, we prove that there is always an optimal topology with minimum interference that is planar. Then, two exact algorithms are proposed. The first one is an exact algorithm to minimize the average interference in polynomial time, O(n 3Δ), where n is the number of nodes and Δ is the maximum node degree. The second one is an exact algorithm to minimize the maximum interference in sub-exponential time, O(n 3ΔO (k)), where k=O(√Δ) is the minimum maximum interference. All the optimal topologies constructed are planar. © 2011 Elsevier B.V. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.titleExact algorithms to minimize interference in wireless sensor networksen_US
dc.typeArticleen_US
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_US
dc.identifier.authorityLau, FCM=rp00221en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/j.tcs.2011.08.041en_US
dc.identifier.scopuseid_2-s2.0-80055032442en_US
dc.identifier.hkuros211441-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80055032442&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume412en_US
dc.identifier.issue50en_US
dc.identifier.spage6913en_US
dc.identifier.epage6925en_US
dc.identifier.isiWOS:000297442600004-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridTan, H=22936378500en_US
dc.identifier.scopusauthoridLou, T=25960811600en_US
dc.identifier.scopusauthoridWang, Y=35222735000en_US
dc.identifier.scopusauthoridHua, QS=15060090400en_US
dc.identifier.scopusauthoridLau, FCM=7102749723en_US
dc.identifier.citeulike9836648-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats