Clusterhead selection in wireless ad hoc networks

Details Clusterhead selection in wireless ad hoc networks Clusterhead selection in wireless ad hoc networks

2001-04-24

2004-12-07

Ho, Duc (Department: 2665)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S256000, C370S400000, C455S445000, C709S241000

Reexamination Certificate

active

06829222

ABSTRACT:

TECHNICAL FIELD
The present invention relates to ad hoc networks, and more particularly, to the selection of clusterheads within ad hoc networks.
BACKGROUND OF THE INVENTION
There are two algorithm design approaches for management of ad hoc networks and routing of packets in such networks. The first choice is to have all nodes maintain knowledge of the network and manage themselves. However, it imposes a significant communication responsibility on individual nodes. Also, communication drains the battery limiting the useful life of these nodes. Each node must dynamically maintain routes to the rest of the nodes in the network. With large networks the number of messages needed to maintain routing tables may cause congestion in the network. Ultimately, this traffic may generate significant delays in message propagation from one node to another.
The second approach is to identify a subset of nodes within the network and vest them with the extra responsibility of being a leader (clusterhead) of certain nodes in their proximity. The clusterheads are responsible for managing communication between nodes within their own cluster as well as routing information to clusterheads in other clusters. Typically, wireless backbones connect clusterheads in the network. Past solutions of this kind have created a hierarchy where every node in the network was no more than one-hop, away from a clusterhead. In large networks this approach may generate a large number of clusterheads and eventually lead to the same problem as stated in the first design choice. Therefore, it is desirable to have control over the clusterhead density in the network. Networks with many clusterheads and few members somewhat defeats the purpose of having a hierarchical structure. However, too few clusterheads will impose a significant load on the clusterheads.
Furthermore, some of the previous clustering solutions have relied on synchronous clocks for exchange of data between nodes. In the Linked Cluster Algorithm, LCA, nodes communicate using TDMA frames. Each frame has a slot for each node in the network to communicate without collisions. For every node to have knowledge of all nodes in its neighborhood it requires 2n TDMA time slots, where n is the number of nodes in the network. Each node broadcasts in its time-slot the nodes that it has heard from, where the time-slots are in ascending order of the node ids. A node A becomes a clusterhead if at least one of the following conditions is satisfied:
1. A has the highest identity among all nodes within 1 wireless hop of it, or
2. A does not have the highest identity in its 1-hop neighborhood, but there exists at least one neighboring node B such that A is the highest identity node in B's 1-hop neighborhood.
Later the LCA heuristic was revised to decrease the number of clusterheads produced in the original LCA. In this revised edition of LCA (LCA
2
) a node is said to be covered if it is in the 1-hop neighborhood of a node that has declared itself to be a clusterhead. Starting from the lowest id node to the highest id node, a node declares itself to be a clusterhead if among the non-covered nodes in its 1-hop neighborhood, it has the lowest id.
The LCA algorithm was developed and intended to be used with small networks of less than 100 nodes. In this case the delay between node transmissions is minimal and may be tolerated. However, as the number of nodes in the network grows larger, LCA will impose greater delays between node transmissions in the TDMA communication scheme and may be unacceptable. Additionally, it has been shown that as communications increase the amount of drift in a synchronous timer also increases, thereby degrading the performance of the overall system or introducing additional delay and overhead.
Other solutions base the election of clusterheads on degree of connectivity, not node id. This approach elects the node with the highest degree of connectivity as a clusterhead. Each node broadcasts the nodes that it can hear, including itself. A node is elected as a clusterhead if it is the highest connected node in all of the uncovered neighboring nodes. In the case of a tie, the lowest or highest id may be used. A node is uncovered if it has not elected a clusterhead yet, otherwise it is covered. A node which has already elected another node as its clusterhead can not also be a clusterhead, As the network topology changes this approach can result in a high turnover of clusterheads. This is because when the highest connectivity node drops even one link due to node movement, it may fail to be re-elected as a clusterhead. This is undesirable due to the high overhead associated with clusterhead change over. Data structures are maintained by the clusterheads for each node in the cluster. As new clusterheads are elected these data structures must be passed from the old clusterhead to the newly elected clusterhead. Re-election of clusterheads could minimize this network traffic and avoid the need to send these data structures. Thus, an improved method for selecting clusterheads which provides better efficiency, stability and fairness is desired.
SUMMARY OF THE INVENTION
The present invention overcomes the foregoing and other problems with a communications network for implementing a method for selecting a clusterhead not greater than d-hops from any node in a cluster within an ad hoc network, wherein d is >1. Each node of the communications network implements a set of rules enabling the selection of a clusterhead for the nodes within a d neighborhood. The rules enable a determination of a largest node identifier and a smallest node identifier. A clusterhead for the d-neighborhood may then be selected for a node responsive to the largest node identifier and smallest node identifier. The nodes are then linked together with the selected clusterhead. The identifiers relating to the above determinations and source nodes of the identifiers are stored within first and second data arrays in each of the nodes.


REFERENCES:
patent: 4864559 (1989-09-01), Perlman
patent: 5583996 (1996-12-01), Tsuchiya
patent: 5659544 (1997-08-01), La Porta et al.
patent: 5850592 (1998-12-01), Ramanathan
patent: 6046978 (2000-04-01), Melnik
patent: 6304556 (2001-10-01), Haas
patent: 6456599 (2002-09-01), Elliott
patent: 6711409 (2004-03-01), Zavgren et al.
D. J. Baker and A. Ephremides, “The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm”,IEEE Transactions on Communications, vol. COM-29, No. 11, pp. 1694-1701, Nov. 1981.
D. J. Baker, A. Ephremides and J. A. Flynn, “The Design and Simulation of a Mobile Radio Network with Distributed Control”,IEEE Journal on Selected Areas in Commications, vol. SAC-2, No. 1, pp. 226-237, Jan. 1984.
B. Das and V. Bharghavan, “Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets”,Proceedings of ICC, 1997.
A. Ephremides, J. E. Wieselthier and D. J. Baker, “A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling”,Proceedings of IEEE, vol. 75, No. 1, pp. 56-73, Jan. 1987.
F. Talucci, M. Gerla and L. Fratta, “MACA-BI (MACA By Invitation): A Receiver Oriented Access Protocol for Wireless Multihop Networks”, Technical Report, University of California at Los Angeles.
E. M. Gafni and D. P. Bertsekas, “Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology”,IEEE Transactions on Communications, vol. COM-29, No. 1, pp. 11-18, Jan. 1981.
M. Gerla and J. T.-C. Tsai, “Multicluster, Mobile, Multimedia Radio Network”,ACMBaltzerJournal of Wireless Networks, pp. 255-265, Jul., 1995.
L. Kleinrock and J. Silvester, “Spatial Reuse in Multiphop Packet Radio Networks”,Proceedings of the IEEE, vol. 75, No. 1, pp. 156-167, Jan. 1987.
A. K. Parekh, “Selecting Routers in Ad-Hoc Wireless Networks”,IEEE, pp 420-424, 1994.
V. D. Park and M. S. Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks”,Proceedings of IEEE INFOCOMApr. 1997.
C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) f

Affiliated with

Also associated with

Rating

Clusterhead selection in wireless ad hoc networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Clusterhead selection in wireless ad hoc networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clusterhead selection in wireless ad hoc networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3292466