Method of electing a leader in an ad-hoc network

• US 7,532,585 B2
• Filed: 10/13/2004
• Issued: 05/12/2009
• Est. Priority Date: 11/04/2003
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Jae-hoon, Han, Youn-hee
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Kang; Suk Jin
• Application Number:
  US10/962,518
• Publication Number:
  US 20050094574A1
• Time in Patent Office: 1,672 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

A method of electing a leader node in an ad-hoc network including a plurality of nodes in the ad-hoc network transmitting node solicitation (NS) messages and calculating distances between the plurality of nodes using information included in the NS messages, determining whether the plurality of nodes are candidate leaders by calculating center position values based on the distances calculated by each of the nodes, and electing the leader node based on information included in leader election option messages transmitted by each candidate leader.

Claims

1. A method of electing a leader node in an ad-hoc network comprising a plurality of nodes, the method comprising:

transmitting node solicitation (NS) messages and calculating distances between the plurality of nodes using information included in the NS messages transmitted from the plurality of nodes;

determining whether the plurality of nodes are candidate leaders by calculating position values of each node based on the distances calculated by each node;

electing the leader node based on information included in leader election option messages transmitted by each of the candidate leaders;

periodically transmitting a hello message indicating that the elected leader node is the leader node;

determining whether each node neighboring the leader node receives a hello message from the leader node;

determining whether each neighboring node qualifies as candidate leader if each neighboring node does not receive the hello message;

transmitting a leader election option message from each neighboring node which qualifies as candidate leader and electing the leader node if at least one neighboring node is determined to be the candidate leader,

wherein no leader election option message is transmitted if no neighboring node qualifies as candidate leader; and

wherein each node that is not candidate leader determines whether the leader election option message is received from other nodes for a predetermined period of time; and

determining each neighboring node to be qualified as candidate leader after the predetermined period of time has elapsed and electing the leader node among candidate leaders.

2. The method as claimed in claim 1, further comprising preparing neighbor node information lists based on the distances calculated by each node,

wherein each node calculates the position values of each node based on the neighbor node information lists.

3. The method as claimed in claim 2, wherein the distances between the plurality of nodes are calculated by a number of hops, which is a number of transmissions of the NS messages from the plurality of nodes using hop limit information included in Internet protocol (IP) headers of the NS messages.

4. The method as claimed in claim 3, wherein the neighbor node information lists of each node includes a number of the plurality of nodes located at a distance corresponding to a number of hops “

K”

from each node, wherein “

K”

is a natural number.

5. The method as claimed in claim 4, wherein the leader election option messages transmitted by each candidate leader include the neighbor node information lists.

6. The method as claimed in claim 5, wherein the candidate leader having a largest value obtained from a following equation, which is calculated according to the neighbor node information lists of each candidate leader, is elected as the leader:

$\underset{K=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_K*N_K$

wherein “

M”

denotes a predetermined natural number, “

α

_K”

denotes a weight value, and “

N_K”

denotes the number of the plurality of nodes located at a distance corresponding to the number of hops “

K”

from the candidate leaders.

7. The method as claimed in claim 3, wherein the nodes that satisfy the following equation are determined as the candidate leaders:

$\underset{K=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_K*N_K\ge <br><br>T$

wherein “

M”

denotes a predetermined natural number, “

T”

denotes a predetermined threshold value, “

α

_K”

denotes a weight value, and “

N_K”

denotes the number of the plurality of nodes located at a distance corresponding to the number of hops “

K”

from the candidate leaders.

8. The method as claimed in claim 1, further comprising:

when a new node takes part in the ad-hoc network, requesting the neighbor node information lists to the plurality of nodes, and preparing an own neighbor node information list; and

the plurality of nodes calculating distances to the new node using information included in a received NS message from the new node and updating the neighbor node information lists, respectively.

9. The method as claimed in claim 1, further comprising transmitting the leader election option message from the leader node to the plurality of nodes of the ad-hoc network if the following equation is satisfied:

$\mathrm{OP}=\underset{K=I}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_K*N_K\rangle <br><br><br><br>T^{\mathrm{\prime <br><br>}}$

wherein OP denotes outer position value, “

I”

denotes a predetermined natural number that is larger than “

1”

, “

M”

denotes a certain natural number that is larger than “

I”

, “

α

K”

denotes a weight value, “

NK”

denotes the number of neighbor nodes located at a distance corresponding to the number of hops “

K”

from the leader node, and “

T”

denotes a predetermined threshold value.

10. The method as claimed in claim 3, wherein a topology of the ad-hoc network is obtained using the number of hops as a representative value of the distance from each node.

11. The method as claimed in claim 2, wherein each node records the neighbor node information lists and updates the neighbor node information lists at a predetermined time interval maintaining the neighbor node information lists updated.

12. The method as claimed in claim 1, wherein the information included in the leader election option message transmitted by each of the candidate leaders includes information about a number of neighbor nodes located at a distance corresponding to a number of hops from a neighbor node information lists.

13. The method as claimed in claim 1, wherein a candidate leader having a largest position value is elected as the leader node.

14. A computer readable medium encoded with processing instructions executed by a processor to perform a method of electing a leader node in an ad-hoc network comprising a plurality of transmitting nodes, the method comprising:

transmitting node solicitation (NS) messages and calculating distances between the plurality of transmitting nodes using information included in the NS messages transmitted from the plurality of transmitting nodes;

determining whether the plurality of transmitting nodes themselves are candidate leaders by calculating position values of each node based on the distances calculated between each of the plurality of transmitting nodes;

electing the leader node based on information included in leader election option messages transmitted by each of the candidate leaders;

periodically transmitting a hello message indicating that the elected leader node is the leader node;

determining whether each node neighboring the leader node receives a hello message from the leader node;

determining whether each neighboring node qualifies as candidate leader if each neighboring node does not receive the hello message;

transmitting a leader election option message from each neighboring node which qualifies as candidate leader and electing the leader node if at least one neighboring node is determined to be the candidate leader,

wherein no leader election option message is transmitted if no neighboring node qualifies as candidate leader; and

wherein each node that is not candidate leader determines whether the leader election option message is received from other nodes for a predetermined period of time; and

determining each neighboring node to be qualified as candidate leader after the predetermined period of time has elapsed and electing the leader node among candidate leaders.

15. The computer readable medium as claimed in claim 14, further comprising preparing neighbor node information lists based on the distances calculated by each of the plurality of transmitting nodes,

wherein each of the plurality of transmitting nodes calculates the position values of each node based on the neighbor node information lists.

16. The computer readable medium as claimed in claim 15, wherein the distances between the plurality of transmitting nodes are calculated by a number of hops, which is a number of transmissions of the NS messages from the plurality of transmitting nodes, using hop limit information included in Internet protocol (IP) headers of the NS messages.

17. The computer readable medium as claimed in claim 16, wherein the neighbor node information lists of each node includes a number of the plurality of transmitting nodes located at a distance corresponding to a number of hops “

K”

from each node, wherein “

K”

is a natural number.

18. The computer readable medium as claimed in claim 17, wherein the leader election option messages transmitted by each candidate leader include the neighbor node information lists.

19. The computer readable medium as claimed in claim 18, wherein the candidate leader having a largest value obtained from a following equation, which is calculated according to the neighbor node information lists of each candidate leader, is elected as the leader node:

$\underset{K=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_K*N_K$

wherein “

M”

denotes a predetermined natural number, “

α

_K”

denotes a weight value, and “

N_K”

denotes the number of transmitting nodes located at a distance corresponding to the number of hops “

K”

from the candidate leaders.

20. The computer readable medium as claimed in claim 16, wherein the plurality of transmitting nodes that satisfy the following equation are determined as the candidate leaders:

$\underset{K=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_K*N_K\ge <br><br>T$

wherein “

M”

denotes a predetermined natural number, “

T”

denotes a predetermined threshold value, “

α

_K”

denotes a weight value, and “

N_K”

denotes the number of transmitting nodes located at a distance corresponding to the number of hops “

K”

from the candidate leaders.

21. The computer readable medium as claimed in claim 14, further comprising:

when a new node takes part in the ad-hoc network, requesting the neighbor node information lists to the plurality of transmitting nodes, and preparing a neighbor node information lists; and

the plurality of transmitting nodes calculating distances to the new node using information included in a received NS message from the new node and updating the neighbor node information lists, respectively.

22. The computer readable medium as claimed in claim 14, further comprising transmitting the leader election option message from the leader node to the plurality of transmitting nodes in the ad-hoc network if the following equation is satisfied:

$\mathrm{OP}=\underset{K=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_K*N_K<br><br>\text{〉<br><br>}<br><br>T^{\mathrm{\prime <br><br>}}$

wherein OP denotes outer position value, “

I”

denotes a predetermined natural number that is larger than “

1”

, “

M”

denotes a certain natural number that is larger than “

I”

, “

α

K”

denotes a weight value, “

NK”

denotes the number of neighbor nodes located at a distance corresponding to the number of hops “

K”

from the leader node, and “

T”

denotes a predetermined threshold value.

23. The computer readable medium as claimed in claim 16, wherein a topology of the ad-hoc network is obtained using the number of hops as a representative value of the distance from each of the plurality of transmitting nodes.

24. The computer readable medium as claimed in claim 15, wherein each of the plurality of transmitting nodes records the neighbor node information lists and updates the neighbor node information lists at a predetermined time interval maintaining the neighbor node information lists updated.

25. The computer readable medium as claimed in claim 14, wherein the information included in the leader election option message transmitted by each of the candidate leaders includes information about a number of neighbor nodes located at a distance corresponding to a number of hops from a neighbor node information lists.

26. The computer readable medium as claimed in claim 14, wherein a candidate leader having a largest position value is elected as the leader node.

27. A method of electing a leader node in an ad-hoc network comprising a plurality of nodes, the method comprising:

transmitting node solicitation (NS) messages and calculating distances between nodes using information included in the NS messages;

determining candidate leaders by calculating position values of each node based on the calculated distances;

electing the leader node based on information included in leader election option messages transmitted by the candidate leaders;

periodically transmitting a hello message indicating that the elected leader node is the leader node;

determining whether each node neighboring the leader node receives a hello message from the leader node;

determining whether each neighboring node qualifies as candidate leader if each neighboring node does not receive the hello message;

transmitting a leader election option message from each neighboring node which qualifies as candidate leader and electing the leader node if at least one neighboring node is determined to be the candidate leader,

wherein no leader election option message is transmitted if no neighboring node qualifies as candidate leader; and

wherein each node that is not candidate leader determines whether the leader election option message is received from other nodes for a predetermined period of time; and

determining each neighboring node to be qualified as candidate leader after the predetermined period of time has elapsed and electing the leader node among candidate leaders.

28. The method as claimed in claim 27, further comprising preparing neighbor node information lists based on the calculated distances,

wherein each node calculates the position values of each node based on the neighbor node information lists.