NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Backbone Construction for Heterogeneous Wireless Ad Hoc Networks
Published
Author(s)
Yi Qian, Hui Guo, Nader Moayeri, Kejie Lu
Abstract
In this paper, we propose a backbone construction scheme over heterogeneous ad hoc networks, where the network nodes have different characteristics such as communication capacity, processing power and energy resource. Most of the wireless backbone construction techniques focus on minimizing the number of backbone nodes. In our proposed scheme, we not only minimize the backbone size, but also take the characteristics of nodes into account when building a backbone. In the scheme, the more capable nodes have higher probability to serve as backbone nodes and provide a wireless highway over which end-to-end communication can take place. The proposed scheme includes two major steps, which can be solved by formulating as a Dominating Set (DS) problem and a Steiner Tree Problem with Minimum Number of Steiner Points (STP-MSP) respectively. We focus on the two subproblems and present a number of polynomial time approximation algorithms. Simulation results show that the proposed scheme achieves higher average backbone node performance, while has approximately the same backbone size comparing with other schemes.
Qian, Y.
, Guo, H.
, Moayeri, N.
and Lu, K.
(2009),
Backbone Construction for Heterogeneous Wireless Ad Hoc Networks, IEEE ICC 2009, Dresden, DE, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=900954
(Accessed October 14, 2025)