File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Minimizing interference for the highway model in wireless ad-hoc and sensor networks
  • 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
Sensor networks
 
Issue Date2011
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationThe 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), Novy Smokovec, Slovakia, 22-28 January 2011. In Lecture Notes in Computer Science, 2011, v. 6543, 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.
 
DescriptionLNCS v. 6543 entitled: SOFSEM 2011: theory and practice of computer science : 37th Conference on Current Trends in Theory and Practice of Computer Science ... 2011 : proceedings
 
ISBN978-364218380-5
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
DOIhttp://dx.doi.org/10.1007/978-3-642-18381-2_43
 
ReferencesReferences in Scopus
 
DC FieldValue
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.descriptionLNCS v. 6543 entitled: SOFSEM 2011: theory and practice of computer science : 37th Conference on Current Trends in Theory and Practice of Computer Science ... 2011 : proceedings
 
dc.identifier.citationThe 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), Novy Smokovec, Slovakia, 22-28 January 2011. In Lecture Notes in Computer Science, 2011, v. 6543, 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.hkuros211556
 
dc.identifier.isbn978-364218380-5
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.scopuseid_2-s2.0-78751673592
 
dc.identifier.spage520
 
dc.identifier.urihttp://hdl.handle.net/10722/151989
 
dc.identifier.volume6543
 
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
 
dc.relation.referencesReferences in Scopus
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.subjectCombinatorial optimization
 
dc.subjectDynamic programming
 
dc.subjectInterference minimization
 
dc.subjectTopology control
 
dc.subjectWireless ad-hoc
 
dc.subjectSensor networks
 
dc.titleMinimizing interference for the highway model in wireless ad-hoc and sensor networks
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Tan, H</contributor.author>
<contributor.author>Lou, T</contributor.author>
<contributor.author>Lau, FCM</contributor.author>
<contributor.author>Wang, Y</contributor.author>
<contributor.author>Chen, S</contributor.author>
<date.accessioned>2012-06-26T06:32:11Z</date.accessioned>
<date.available>2012-06-26T06:32:11Z</date.available>
<date.issued>2011</date.issued>
<identifier.citation>The 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), Novy Smokovec, Slovakia, 22-28 January 2011. In Lecture Notes in Computer Science, 2011, v. 6543, p. 520-532</identifier.citation>
<identifier.isbn>978-364218380-5</identifier.isbn>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/151989</identifier.uri>
<description>LNCS v. 6543 entitled: SOFSEM 2011: theory and practice of computer science : 37th Conference on Current Trends in Theory and Practice of Computer Science ... 2011 : proceedings</description>
<description.abstract>Finding 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&apos; 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 &#916; 3), where n is the number of nodes and &#916; is the maximum node degree. The other algorithm constructs the optimal topology that minimizes the maximum interference in sub-exponential time, O(n 3&#916; O(k)), where is the minimum maximum interference. &#169; 2011 Springer-Verlag Berlin Heidelberg.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<subject>Combinatorial optimization</subject>
<subject>Dynamic programming</subject>
<subject>Interference minimization</subject>
<subject>Topology control</subject>
<subject>Wireless ad-hoc</subject>
<subject>Sensor networks</subject>
<title>Minimizing interference for the highway model in wireless ad-hoc and sensor networks</title>
<type>Conference_Paper</type>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1007/978-3-642-18381-2_43</identifier.doi>
<identifier.scopus>eid_2-s2.0-78751673592</identifier.scopus>
<identifier.hkuros>211556</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-78751673592&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>6543</identifier.volume>
<identifier.spage>520</identifier.spage>
<identifier.epage>532</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Tsinghua University