Cluster head election in an ad-hoc network

• US 8,134,950 B2
• Filed: 04/03/2007
• Issued: 03/13/2012
• Est. Priority Date: 04/03/2007
• Status: Active Grant

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Pun, Ngan-cheung
• Primary Examiner(s): Kincaid, Lester
• Assistant Examiner(s): WOO, KUO-KONG
• Application Number:
  US11/695,835
• Publication Number:
  US 20080247353A1
• Time in Patent Office: 1,806 Days
• Field of Search: 455/445, 455/7, 370/238, 370/338, 370/328, 370/256, 709/227
• US Class Current: 370/328
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

The ad-hoc network includes a plurality of mobile nodes including at least one group of mobile nodes operating as a cluster with a currently elected cluster head node. The mobile nodes include a controller and a wireless communications device cooperating therewith to determine whether the currently elected cluster head node appears inactive and then initiate a token-based cluster head node election based thereon. During the token-based cluster head node election, the cluster mobile nodes generate and transmit tokens having respective token weights, receive tokens from neighboring nodes, selectively retransmit the tokens based upon the token weights, and elect a new cluster head node based upon the token weights.

Claims

1. A mobile ad-hoc network comprising:

a plurality of mobile nodes including at least one group of mobile nodes operating as a cluster with a currently elected cluster head node;

each mobile node comprising a controller and a wireless communications device configured to cooperate therewith to determine whether the currently elected cluster head node appears inactive based upon failing to overhear a response message from the currently elected cluster head node, sending a confirmation request message to the currently elected cluster head node, and failing to receive a confirmation message from the currently elected cluster head node, and initiate a token-based cluster head node election based thereon during which the cluster mobile nodes are configured to

generate and transmit tokens having respective token weights,

receive tokens from neighboring nodes,

selectively retransmit the tokens based upon the token weights, and

elect a new cluster head node based upon the token weights.

2. The mobile ad-hoc network according to claim 1 wherein the controller and the wireless communications device cooperate to determine whether the currently elected cluster head node appears inactive based upon failing to receive a status message from the currently elected cluster head node for a predetermined time period.

3. The mobile ad-hoc network according to claim 1 wherein the controller and the wireless communications device cooperating to determine whether the currently elected cluster head node appears inactive further includes determining the presence of at least one neighbor node.

4. The mobile ad-hoc network according to claim 1 wherein the tokens comprise respective election messages each including a node ID and a parameter value.

5. The mobile ad-hoc network according to claim 4 wherein the parameter value indicates a number of neighbor nodes of the corresponding cluster node.

6. The mobile ad-hoc network according to claim 4 wherein the associated token weight is defined by a weight value based upon the node ID and the parameter value.

7. The mobile ad-hoc network according to claim 6 wherein the controller and wireless communications device cooperate to retransmit a best token defined as the received token with a highest weight value.

8. The mobile ad-hoc network according to claim 7 wherein the controller stores the node ID of the best token as the cluster head node ID.

9. The mobile ad-hoc network according to claim 4 wherein the election message further includes a group ID defining a boundary for transmission of the token.

10. The mobile ad-hoc network according to claim 9 wherein the election message further includes a time-to-live field defining a number of times the token can be transmitted.

11. A mobile node for operation in a cluster of mobile nodes within in ad-hoc network, the cluster including a currently elected cluster head node, the mobile node comprising:

a controller and a wireless communications device configured to cooperate therewith to determine whether the currently elected cluster head node appears inactive based upon failing to overhear a response message from the currently elected cluster head node, sending a confirmation request message to the currently elected cluster head node, and failing to receive a confirmation message from the currently elected cluster head node, and to initiate a token-based cluster head node election based thereon including

generating and transmitting a token having a token weight,

receiving tokens from neighboring nodes,

selectively retransmitting the tokens based upon the token weights, and

electing a new cluster head node based upon the token weights.

12. The mobile node according to claim 11 wherein the controller and the wireless communications device cooperate to determine whether the currently elected cluster head node appears inactive based upon failing to receive a status message from the currently elected cluster head node for a predetermined time period.

13. The mobile node according to claim 11 wherein the tokens comprise respective election messages each including a node ID and a parameter value.

14. The mobile node according to claim 13 wherein the parameter value indicates a number of neighbor nodes of the corresponding cluster node.

15. The mobile node according to claim 13 wherein the associated token weight is defined by a weight value based upon the node ID and the parameter value;

wherein the controller and wireless communications device cooperate to retransmit a best token defined as the received token with a highest weight value; and

wherein the controller stores the node ID of the best token as the cluster head node ID.

16. The mobile node according to claim 14 wherein the election message further includes a group ID defining a boundary for transmission of the token.

17. The mobile node according to claim 16 wherein the election message further includes a time-to-live field defining a number of times the token can be transmitted.

18. A method of electing a cluster head node for a group of mobile nodes operating as a cluster within a mobile ad-hoc network, the method comprising:

determining whether the currently elected cluster head node appears inactive based upon failing to overhear a response message from the currently elected cluster head node, sending a confirmation request message to the currently elected cluster head node, and failing to receive a confirmation message from the currently elected cluster head node; and

initiating a token-based cluster head node election based upon the determination during which the cluster mobile nodes

generate and transmit tokens having respective token weights,

receive tokens from neighboring nodes,

selectively retransmit the tokens based upon the token weights, and

elect a new cluster head node based upon the token weights.

19. The method according to claim 18 wherein determining whether the currently elected cluster head node appears inactive is based upon failing to receive a status message from the currently elected cluster head node for a predetermined time period.

20. The method according to claim 18 wherein the tokens comprise respective election messages each including a node ID and a parameter value.

21. The method according to claim 20 wherein the parameter value indicates a number of neighbor nodes of the corresponding cluster node.

22. The method according to claim 20 wherein the associated token weight is defined by a weight value based upon the node ID and the parameter value.

23. The method according to claim 22 wherein selectively retransmit the tokens comprises retransmitting a best token defined as the received token with a highest weight value.

24. The method according to claim 23 further comprising storing the node ID of the best token as the cluster head node ID.

25. The method according to claim 20 wherein the election message further includes a group ID defining a boundary for transmission of the token.

26. The method according to claim 25 wherein the election message further includes a time-to-live field defining a number of times the token can be transmitted.