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

Title | Minimizing interference for the highway model in wireless ad-hoc and sensor networks |
---|---|

Authors | Tan, H1 Lou, T2 Lau, FCM1 Wang, Y2 Chen, S2 |

Keywords | Combinatorial optimization Dynamic programming Interference minimization Topology control Wireless ad-hoc Sensor networks |

Issue Date | 2011 |

Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |

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 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-642-18381-2_43 |

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' 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. |

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 |

ISBN | 978-364218380-5 |

ISSN | 0302-9743 2013 SCImago Journal Rankings: 0.310 |

DOI | http://dx.doi.org/10.1007/978-3-642-18381-2_43 |

References | References in Scopus |

DC Field | Value |
---|---|

dc.contributor.author | Tan, H |

dc.contributor.author | Lou, T |

dc.contributor.author | Lau, FCM |

dc.contributor.author | Wang, Y |

dc.contributor.author | Chen, S |

dc.date.accessioned | 2012-06-26T06:32:11Z |

dc.date.available | 2012-06-26T06:32:11Z |

dc.date.issued | 2011 |

dc.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' 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.nature | Link_to_subscribed_fulltext |

dc.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 |

dc.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 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-642-18381-2_43 |

dc.identifier.doi | http://dx.doi.org/10.1007/978-3-642-18381-2_43 |

dc.identifier.epage | 532 |

dc.identifier.hkuros | 211556 |

dc.identifier.isbn | 978-364218380-5 |

dc.identifier.issn | 0302-9743 2013 SCImago Journal Rankings: 0.310 |

dc.identifier.scopus | eid_2-s2.0-78751673592 |

dc.identifier.spage | 520 |

dc.identifier.uri | http://hdl.handle.net/10722/151989 |

dc.identifier.volume | 6543 |

dc.language | eng |

dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |

dc.publisher.place | Germany |

dc.relation.ispartof | Lecture Notes in Computer Science |

dc.relation.references | References in Scopus |

dc.rights | The original publication is available at www.springerlink.com |

dc.subject | Combinatorial optimization |

dc.subject | Dynamic programming |

dc.subject | Interference minimization |

dc.subject | Topology control |

dc.subject | Wireless ad-hoc |

dc.subject | Sensor networks |

dc.title | Minimizing interference for the highway model in wireless ad-hoc and sensor networks |

dc.type | Conference_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' 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.</description.abstract> <language>eng</language> <publisher>Springer Verlag. The Journal'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&selection=ref&src=s&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

- The University of Hong Kong
- Tsinghua University