Conference Paper: Minimizing interference for the highway model in wireless ad-hoc and sensor networks

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleMinimizing interference for the highway model in wireless ad-hoc and sensor networks
AuthorsTan, H1
Lou, T2
Lau, FCM1
Wang, Y2
Chen, S2
KeywordsCombinatorial Optimization
Dynamic Programming
Interference Minimization
Topology Control
Wireless Ad-Hoc And Sensor Networks
Issue Date2011
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
CitationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2011, v. 6543 LNCS, p. 520-532 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-18381-2_43
AbstractFinding a low-interference connected topology is one of the fundamental problems in wireless ad-hoc and sensor networks. The receiver-centric interference on a node is the number of other nodes whose transmission ranges cover the node. The problem of reducing interference through adjusting the nodes' transmission ranges in a connected network can be formulated as that of connecting the nodes by a spanning tree while minimizing interference. In this paper, we study minimization of the average interference and the maximum interference for the high-way model, where all the nodes are arbitrarily distributed on a line. Two exact algorithms are proposed. One constructs the optimal topology that minimizes the average interference among all the nodes in polynomial time, O(n 3 Δ3), where n is the number of nodes and Δ is the maximum node degree. The other algorithm constructs the optimal topology that minimizes the maximum interference in sub-exponential time, O(n 3Δ O(k)), where is the minimum maximum interference. © 2011 Springer-Verlag Berlin Heidelberg.
ISSN0302-9743
2011 SCImago Journal Rankings: 0.034
DOIhttp://dx.doi.org/10.1007/978-3-642-18381-2_43
ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorTan, H
dc.contributor.authorLou, T
dc.contributor.authorLau, FCM
dc.contributor.authorWang, Y
dc.contributor.authorChen, S
dc.date.accessioned2012-06-26T06:32:11Z
dc.date.available2012-06-26T06:32:11Z
dc.date.issued2011
dc.description.abstractFinding a low-interference connected topology is one of the fundamental problems in wireless ad-hoc and sensor networks. The receiver-centric interference on a node is the number of other nodes whose transmission ranges cover the node. The problem of reducing interference through adjusting the nodes' transmission ranges in a connected network can be formulated as that of connecting the nodes by a spanning tree while minimizing interference. In this paper, we study minimization of the average interference and the maximum interference for the high-way model, where all the nodes are arbitrarily distributed on a line. Two exact algorithms are proposed. One constructs the optimal topology that minimizes the average interference among all the nodes in polynomial time, O(n 3 Δ3), where n is the number of nodes and Δ is the maximum node degree. The other algorithm constructs the optimal topology that minimizes the maximum interference in sub-exponential time, O(n 3Δ O(k)), where is the minimum maximum interference. © 2011 Springer-Verlag Berlin Heidelberg.
dc.description.natureLink_to_subscribed_fulltext
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2011, v. 6543 LNCS, p. 520-532 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-18381-2_43
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-18381-2_43
dc.identifier.epage532
dc.identifier.issn0302-9743
2011 SCImago Journal Rankings: 0.034
dc.identifier.scopuseid_2-s2.0-78751673592
dc.identifier.spage520
dc.identifier.urihttp://hdl.handle.net/10722/151989
dc.identifier.volume6543 LNCS
dc.languageeng
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
dc.publisher.placeGermany
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.relation.referencesReferences in Scopus
dc.subjectCombinatorial Optimization
dc.subjectDynamic Programming
dc.subjectInterference Minimization
dc.subjectTopology Control
dc.subjectWireless Ad-Hoc And Sensor Networks
dc.titleMinimizing interference for the highway model in wireless ad-hoc and sensor networks
dc.typeConference_Paper
Author Affiliations
  1. The University of Hong Kong
  2. Tsinghua University