Method of electing a leader in an ad-hoc network

• US 20050094574A1
• Filed: 10/13/2004
• Published: 05/05/2005
• 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
• Granted Patent: US 7,532,585 B2
• Time in Patent Office: Days
• 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 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 transmitted from the plurality of nodes;

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

electing the leader node based on information included in leader election option messages transmitted by each of the 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 center position values 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 node include the neighbor node information lists.

6. The method as claimed in claim 5, wherein the candidate node having a largest value obtained from a following equation, which is calculated according to the neighbor node information lists of each candidate node, 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 nodes.

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

$\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 nodes.

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

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

determining whether each node that has failed to receive the hello message is itself the candidate leader based on the neighbor node information lists; and

determining the node that is not to be the candidate leader to be the candidate node if the node has failed to receive the leader election option message from any other candidate node for a predetermined time.

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

a new node taking 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.

10. The method as claimed in claim 1, further comprising the leader node transmitting the leader election option message 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 “

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, “

N_K”

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.

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

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

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

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

15. A computer readable medium encoded with processing instructions performing a method of electing a leader node in an ad-hoc network, the method comprising:

a plurality of transmitting nodes in the ad-hoc network 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 center position values based on the distances calculated between each of the plurality of transmitting nodes; and

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

16. The computer readable medium as claimed in claim 15, 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 center position values based on the neighbor node information lists.

17. The computer readable medium as claimed in claim 16, 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.

18. The computer readable medium as claimed in claim 17, 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.

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

20. The computer readable medium as claimed in claim 19, wherein the candidate node having a largest value obtained from a following equation, which is calculated according to the neighbor node information lists of each candidate node, 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 nodes.

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

$\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 nodes.

22. The computer readable medium as claimed in claim 15, further comprising:

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

each of the plurality of nodes that has failed to receive the hello message determining whether the node itself is the candidate leader based on the neighbor node information lists; and

the node that is determined not to be the candidate leader determined to be the candidate node if the node has failed to receive the leader election option message from any other candidate node for a predetermined time.

23. The computer readable medium as claimed in claim 15, further comprising:

a new node taking 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.

24. The computer readable medium as claimed in claim 15, further comprising the leader node transmitting the leader election option message 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 “

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.

25. The computer readable medium as claimed in claim 17, 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.

26. The computer readable medium as claimed in claim 16, 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.

27. The computer readable medium as claimed in claim 15, 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.

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

29. A method of electing a leader node in an ad-hoc network comprising:

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

determining candidate leaders by calculating center position values based on the calculated distances; and

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

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

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