US 7,532,585 B2Grant

Method of electing a leader in an ad-hoc network

Issue Date:2009-05-12

•28 Claims

•6 Drawing Sheets

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.

Metadata

Assignee

Samsung Electronics Co., Ltd.

Inventors

Jae-hoon Kim
Youn-hee Han

Application Information

Application Number:US 10/962,518

Filing Date:2004-10-13

Priority Date:2003-11-04

Art Unit:2419

Classifications

IPC:

H04L12/28

Patent Drawings (6 sheets)

Description

Cross-Reference to Related Application

[0001] This application claims the priority of Korean Patent Application No. 2003-77700 filed Nov. 4, 2003 in the Korean Intellectual Property Office, the disclosure of which is incorporated herein by reference.

Background of the Invention

[0002] 1. Field of the Invention

[0003] The present invention generally relates to a method of electing a leader in an ad-hoc network. More particularly, the present invention relates to a method of electing a leader node in an ad-hoc network capable of electing a suitable leader node in accordance with the circumstances such as the creation of an ad-hoc network, topology change of the ad-hoc network, and movement of a general node and the leader node.

[0004] 2. Description of the Related Art

[0005] With the development of mobile communication appliances and communication techniques, in addition to the existing infrastructure network, the necessity for a small-sized wireless communication network has increased. Specifically, in environments where the network is isolated from an external Internet and no wire equipment is provided, for example, in a state of emergency, in an airplane, in a building, or in a mountainous region, a small-sized wireless communication network such as an ad-hoc network is greatly required.

[0006] In the ad-hoc network, unlike the infrastructure network, a router that repeats a packet transmission/reception does not exist separately, but each mobile node serves as a host and a router simultaneously. Since a node in the ad-hoc network is provided with wireless communication equipment, the movement of the node from one ad-hoc network to another network becomes possible, and this causes the topology of the ad-hoc network to be changed.

[0007] In the ad-hoc network, the transmission range of radio waves for each node is limited, and thus a packet may not be directly transmitted from its departure node to its destination node. In this case, the packet is transmitted via a plurality of nodes that serve as routers. This system is called a multi-hop system, and a routing protocol for implementing the multi-hop system is required in the ad-hoc network.

[0008] A node that takes part in the ad-hoc network should be allocated with an address to be used in the corresponding ad-hoc network. For this, the node generates a temporary address in the same manner as an automatic address generation, and performs a Duplicate Address Detection (DAD) to confirm whether the generated address is the sole address in the corresponding ad-hoc network.

[0009] The DAD starts when the node floods a Neighbor Solicitation (NS) message that includes an address generated by the node itself into the whole network, and succeeds if the node fails to receive a Neighbor Advertisement (NA) message from a node that uses the same address within a time limit. If the DAD succeeds, the corresponding node performs a communication in the ad-hoc network using the confirmed address.

[0010] Since a fixed router does not exist separately in the ad-hoc network and each node serves as a router and a host simultaneously, the communication between the nodes is performed without any central control. The communication between the nodes is performed in a manner that a departure node transmits a desired packet to the whole network and a designated destination node receives the packet directly or via another node.

[0011] Technical research in the ad-hoc network field has mainly been made with respect to an efficient routing method such as a method of supporting a network environment using an Internet Protocol (IP) that is an Internet addressing system. However, research for the configuration and management of an ad-hoc network is actively being performed.

[0012] Accordingly, by introducing the concept of a leader node for the configuration and management of the ad-hoc network, the DAD is efficiently performed in the ad-hoc network and an easy scalability of the network is sought by sending a Router Advertisement (RA) message.

[0013] There is no dominance among nodes that independently perform their communications as simultaneously serving as routers and hosts in the ad-hoc network. Thus, a leader node has to be elected among the nodes suitable to serve as a leader node in accordance with a certain method.

[0014] There is a conventional method of electing a leader node that gives a predetermined number to each node that takes part in the ad-hoc network as an Identification (ID) and elects the leader node by comparing such IDs with one another. However, since these IDs are given irrespective of the positions of each node according to the topology of the ad-hoc network, the leader node electing method does not reflect the topology of the network. Thus, the leader node elected by the conventional method cannot contribute to the transmission of the RA message and the shortening of time for the DAD performing transmission.

[0015] There is another conventional method, which elects a node having the largest number of neighbor nodes as a leader node. Such a leader node electing method uses information on neighbor nodes in order to elect the leader node, but it does not consider the topology of the whole ad-hoc network. Accordingly, it has the drawback in that it cannot reflect the topology of the whole ad-hoc network. When the leader node becomes unsuitable for its own role due to the change of the topology of the network and the change of the number of neighbor nodes for each node, because the leader node once elected cannot be replaced, the conventional method cannot cope with the change of the network topology.

[0016] In addition to the two above-described conventional methods of electing a leader node, there is another leader node electing method based on a Temporally-Ordered Routing Algorithm (TORA), that is, an ad-hoc routing protocol. However, this method, being based on a predetermined routing protocol, is inapplicable to other routing protocols except for the TORA.

Summary of the Invention

[0017] An aspect of the present invention is to solve at least the above and/or other problems and disadvantages and to provide at least the advantages described below.

[0018] According to an aspect of the present invention, there is provided a method of electing a leader node in an ad-hoc network that can variably elect a suitable leader node in accordance with circumstances such as topology change of the ad-hoc network, and movement of a general node and the leader node, by reflecting the topology of the ad-hoc network and determining the suitability of the elected leader node according to the topology change of the network.

[0019] The foregoing and/or other objects and advantages are substantially realized by providing a method of electing a leader node in an ad-hoc network, according to certain embodiments of the present invention, including calculating distances to transmitting nodes that transmit node solicitation (NS) messages using information included in the NS messages transmitted by the transmitting nodes from a plurality of nodes in the ad-hoc network, determining whether the nodes themselves 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 candidate leader.

[0020] According to the aspect of the present invention, the method further includes preparing neighbor node information lists based on distances calculated by each node. The distances are calculated by the numbers of hops, which are the numbers of transmissions of the NS messages from the transmitting nodes, using hop limit information included in Internet protocol (IP) headers of the NS messages.

[0021] According to an aspect of the present invention, the neighbor node information list of each node includes the number of the transmitting nodes located at a distance corresponding to the number of hops “K” from each node, wherein “K” is a natural number. The leader election option messages transmitted by each candidate node include the neighbor node information lists.

[0022] According to an aspect of the present invention, the candidate node having the 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:

[0023]

\sum_{K = 1}^{M} α_{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.

[0024] According to an aspect of the present invention, the nodes that satisfy the following equation are determined as the candidate nodes:

[0025]

\sum_{K = 1}^{M} α_{K} * N_{K} \geq 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.

[0026] According to an aspect of the present invention, the method includes the elected leader periodically transmitting a hello message informing that the elected node is the leader, each node that has failed to receive the hello message determining whether the node itself is the candidate leader based on the neighbor node information list, and the node that is determined not to be the candidate leader determining 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.

[0027] According to an aspect of the present invention, the method includes a new node taking part in the ad-hoc network and transmitting an NS message, requesting the neighbor node information lists to the other existing nodes, and preparing its own neighbor node information list, and the existing nodes calculating distances to the new node using information included in the received NS message from the new node and updating their neighbor node information lists, respectively.

[0028] According to an aspect of the present invention, the method includes the leader node transmitting the leader election option message if it satisfies the following equation:

[0029]

OP = \sum_{K = I}^{M} α_{K} * N_{K} 〉 T^{'}

wherein “I” denotes a predetermined natural number larger than “1”, “M” denotes a certain natural number 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.

[0030] According to another aspect of the present invention, there is provided a computer readable medium encoded with processing instructions performing a method of electing a leader node in an ad-hoc network, the method including: 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.

[0031] Additional aspects and/or advantages of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.

Brief Description of the Drawings

[0032] These and/or other aspects and advantages of the invention will become apparent and more readily appreciated from the following description of the embodiments, taken in conjunction with the accompanying drawings of which:

[0033] FIG. 1 is a flowchart illustrating a method of electing a leader node in an ad-hoc network according to an embodiment of the present invention;

[0034] FIG. 2 is a view illustrating an example of a neighbor node information list kept by a respective node in the ad-hoc network;

[0035] FIG. 3 is a view illustrating an example of a leader election option message according to an embodiment of the present invention;

[0036] FIG. 4A is a view illustrating an example of the ad-hoc network according to an embodiment of the present invention;

[0037] FIG. 4B is a view illustrating an example of a neighbor information list of a predetermined node of FIG. 4A;

[0038] FIG. 5 is flowchart illustrating a method of electing a new leader node when a leader node moves in the ad-hoc network according to an embodiment of the present invention; and

[0039] FIG. 6 is flowchart illustrating a method of electing a new leader node in accordance with the topology change of the ad-hoc network according to an embodiment of the present invention.

Detailed Description of the Embodiments

[0040] Reference will now be made in detail to the embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below to explain the present invention by referring to the figures.

[0041] FIG. 1 is a flowchart illustrating a method of electing a leader node in an ad-hoc network according to an embodiment of the present invention. Referring to FIG. 1, a node, which takes part in an ad-hoc network when the network is created, generates its own address to be used in the network and transmits a Neighbor Solicitation (NS) message that includes an address generated to perform a Duplicate Address Detection (DAD), to the whole network at operation S110. Accordingly, each node receives the NS message from all nodes that take part in the network.

[0042] Each node of the ad-hoc network receives the NS message and calculates a distance to a transmitting node that transmitted the NS message using information included in the NS message at operation S120. The NS message according to an embodiment of present invention includes hop limit information in its IP header. Accordingly, each node can calculate the number of hops of a path through which the NS message from the transmitting node is transmitted using the hop limit information included in the NS message.

[0043] The range of one hop in the ad-hoc network is related to a transmission range of each node, and the number of hops among nodes in the ad-hoc network is closely related to a time required for the communication. Thus, the actual topology of the ad-hoc network can be reflected using the calculated number of hops as a representative value of the distance from each node to each transmitting node.

[0044] Since each node of the ad-hoc network receives the NS message from other nodes, each node can calculate the number of hops to the all other nodes and prepare the neighbor node information list using the number of hops at operation S130. Each node calculates information such as the number of neighbor nodes located at a distance of one hop from the node, and the number of neighbor nodes located at a distance of two hops from the node, based on the number of hops to other nodes, and records the numbers of hops in the neighbor node information list.

[0045] FIG. 2 is a view illustrating an example of a neighbor node information list kept by a respective node in the ad-hoc network. Referring to FIG. 2, the number of neighbor nodes located at a one-hop to 10-hop distances from the corresponding node is recorded in the neighbor node information list. Information in a range wider than the above-described example may be recorded in the neighbor node information list in consideration of the size, and environment of the ad-hoc network. Each node records the neighbor node information list and updates the neighbor node information list at a predetermined time interval so as to maintain the newest information.

[0046] Then, each node calculates its own center position value in the network based on the number of nodes located at distances corresponding to each hop recorded in the neighbor node information list at operation S140. The center position value is calculated by the following equation 1:

[0047]

\begin{matrix} P = \sum_{K = 1}^{M} α_{K} * N_{K} & [Equation 1] \end{matrix}

wherein “M” denotes a certain natural number, “α_K” denotes a weight value (a₁≠a₂≠a₃≠a₄≠ . . . α_K), and “N_K” denotes the number of transmitting nodes located at a distance corresponding to the number of hops “K” from the corresponding nodes. The weight value “α_K” can be determined according to the characteristic of the ad-hoc network.

[0048] For example, of “M=3”, the center position value “P” becomes “P=α₁×N₁+α₂×N₂+α₃×N₃”. Each node compares the calculated center position value “P” with the threshold value “T”, and if the center position value “P” is equal to or larger than the threshold value “T”, the node determines itself as the candidate leader at operation S150. The threshold value “T”, for example, may be “5”.

[0049] Each node that determined itself as the candidate leader transmits the leader election optional message to the whole network at operation S160.

[0050] FIG. 3 is a view illustrating an example of a leader election option message according to an embodiment of the present invention. Referring to FIG. 3, the candidate leader includes information about the number of neighbor nodes located at a distance corresponding to the number of hops of its own neighbor node information list, in the leader election option message to transmit the message. The candidate leader also informs that the candidate leader itself is the leader by setting an “L” bit as shown in FIG. 3.

[0051] Upon receiving the leader election option message from another candidate leader, the candidate leader calculates the center position value of the candidate leader using the information included in the received leader election option message, and compares the calculated center position value with its own center position value. The candidate leader receives the leader election option message and gives up becoming the leader node, that is, determines itself not the leader node, if its center position value is smaller than the center position value of the other candidate leader. As a result, the candidate node that has the largest center position value is elected as the leader node at operation S170.

[0052] FIG. 4A is a view illustrating an example of the ad-hoc network according to an embodiment of the present invention, and FIG. 4B is a view illustrating an example of a neighbor information list of a predetermined node of FIG. 4A. Referring to FIGS. 4A and 4B, the ad-hoc network includes 1^stthrough 16^thnodes 401 through 416.

[0053] When the ad-hoc network is created, each node transmits the NS message to the whole network. Each node also calculates the number of hops to other nodes by using the information included in the NS messages received from other nodes, and prepares the neighbor node information list using the calculated number of hops.

[0054] Each node calculates its own center position value using the information recorded in its own neighbor node information list, and if the center position value is more than a predetermined number, for example, more than “5”, the node determines itself to be the candidate leader. FIG. 4B illustrates the neighbor node information list kept by the 6^th, 7^thand 12^thnodes 406, 407 and 412 that are the candidate leaders.

[0055] For example, the weight value α_Kin the equation 1 is set to “1”, the natural number “M” is set to “3”, and the threshold value “T” is set to “5”. Accordingly, the center position value of the 6^thnode 406 calculated by using the neighbor node information list is “1×4+1×7+1×4=15”, the center position value of the 7^thnode 407 is “1×4+1×5+1×4=13”, and the center position value of the 12^thnode 412 is “1×4+1×4+1×3=11”. As a result, all the center position values of the 6^th, 7^thand 12^thnodes 406, 407 and 412 are larger than “5”, and thus they are determined as the candidate leaders.

[0056] The 6^th, 7^thand 12^thnodes 406, 407 and 412, which are the candidate leaders, transmit the leader election option messages including their own neighbor node information to the whole network. Each candidate leader calculates the center position values of other candidate leaders using the information included in the received leader election option messages, and compares with its own center position value.

[0057] The 7^thnode 407 has its center position value of “13”, which is smaller than the center position value “15” of the 6^thnode 406 according to the information included in the leader election option message received from the 6^thnode 406. Thus, the 7^thnode 407 gives up becoming the leader.

[0058] The 12^thnode 412 has the center position value of “11”, which is smaller than the center position values “15” or “13” of the 6^thnode 406 and the 7^thnode 407 according to the information included in the leader election option messages received from the 6^thnode 406 and the 7^thnode 407, respectively. Thus, the 12^thnode 412 gives up becoming the leader.

[0059] The 6^thnode 406 has the center position value of “15”, which is larger than the center position values “13” or “11”of the 7^thnode 407 and the 12^thnode 412 according to the information included in the leader election option messages received from the 7^thnode 407 and the 12^thnode, respectively. Thus, the 6^thnode is elected as the leader.

[0060] FIG. 5 is flowchart illustrating a method of electing a new leader node when a leader node moves in the ad-hoc network according to an embodiment of the present invention. Since each node in the ad-hoc network has mobility, the leader node may also move from the present network to another ad-hoc network. If the leader node leaves the network, a new leader should be elected. The leader node electing method in this case will be described with reference to FIG. 5.

[0061] The leader node periodically transmits a hello message to the whole network at operation S510. According to a Mobile Ad-hoc Network (MANET) routing protocol, the hello message is used to maintain the neighbor node information. The leader node according to an embodiment of the present invention may periodically transmit the hello message, while indicating that the node itself is the leader node. Each neighbor node determines whether the hello message is received from the leader node at operation S520 and confirms the existence of the leader node. If each neighbor node fails to receive the hello message from the leader node, the neighbor nodes can detect the movement of the leader node.

[0062] If the hello message is not received from the leader node, the neighbor node of the leader node detects the movement of the leader node and determines whether itself is the candidate leader at operation S530. The method of determining whether the node itself is the candidate leader is as described above. If there is any node determined as the candidate leader, the corresponding candidate leader transmits the leader election option message to the whole network at operation S550, and the leader node is elected among the candidate leaders as described above at operation S560.

[0063] Each node that is not the candidate leader determines whether the leader election option message is received from other nodes for a predetermined time (Random_Delay_Time) at operation S540. If there is no candidate leader among the neighbor nodes, the neighbor node could not receive the leader election option message until the predetermined time elapses. Accordingly, the neighbor node determines itself as the candidate leader and transmits the leader election option message at operation S550, and the leader node is elected among the candidate leaders at operation S560.

[0064] FIG. 6 is flowchart illustrating a method of electing a new leader node in accordance with the topology change of the ad-hoc network according to an embodiment of the present invention. The topology of the network may change due to various reasons such as a new node taking part in the presently created ad-hoc network.

[0065] If a new node takes part in the ad-hoc network, the corresponding node transmits an NS message to the whole network so as to perform the DAD. The existing nodes in the ad-hoc network receive the transmitted NS message and update their own neighbor node information lists using the information included in the NS message. The new node requests and receives the neighbor node information lists from the existing nodes, and prepares its own neighbor node information list using the received neighbor node information lists.

[0066] If the neighbor node information list is updated by the new node taking part in the network, the leader node calculates its own outer position value at operation S610. The outer position value “OP” is defined by the following equation 2:

[0067]

\begin{matrix} OP = \sum_{K = I}^{M} α_{K} * N_{K} & [Equation 2] \end{matrix}

wherein “I” denotes a natural number that is larger than “1”, “M” denotes a certain natural number that is larger than “I”, “α_K” denotes a weight value (a₁≠a₂≠a₃≠a₄ ≠. . . α_K, or they may be equal to one another), and “N_K” denotes the number of neighbor nodes located at a distance corresponding to the number of hops “K” from the corresponding node. The weight value “α_K” can be determined according to the characteristic of the ad-hoc network and is not limited to the embodiments of the present invention.

[0068] For example, if “I=4”, “M=10” and “α_K=1”, the outer position value “OP” of the leader node becomes “OP=α₄×N₄+α₅×N₅+α₆×N₆”+ . . . +α₁₀×N₁₀”.

[0069] The leader node compares the calculated outer position value with the threshold value “T” at operation S620, and if the outer position value “OP” is larger than the threshold value “T”, the leader node transmits the leader election option message to the whole network in order to re-elect the leader node at operation S630. For example, the threshold value “T” may be “10”.

[0070] Each node, which has received the leader election option message from the leader node, compares the center position value of the leader node with the center position value of its own neighbor node information list after subtracting the outer position value from its own center position value. If the value obtained by subtracting the outer position value from its own center position value is larger than the center position value of the leader node, the node determines to be the candidate leader and transmits the leader election option message with the “L” bit set, to the whole network.

[0071] The candidate leader is finally elected as the leader node if no leader election option message is transmitted from other candidate leaders for the predetermined time or if it is determined that its own center position value is larger than that of any other candidate leader through the comparison of its own center position value with the information included in the leader election option messages transmitted from other candidate leaders at operation S640.

[0072] As described above, in the method of electing a leader node in an ad-hoc network according to an embodiment of the present invention, an efficient management of the ad-hoc network becomes possible. Accordingly, a suitable leader node is elected in accordance with the changes in the circumstances such as the creation of an ad-hoc network, topology change of the ad-hoc network, and movement of a general node and the leader node. Furthermore, the DAD is rapidly performed using the elected leader node or the elected leader node is applied to the network extension.

[0073] Also, the method according to an embodiment of the present invention can be applied to the merge of the network or the DAD among the networks, and also to the regional division or clustering of the ad-hoc network.

[0074] The aforementioned method of electing a leader node in an ad-hoc network may be embodied as a computer program that can be run by a computer, which can be a general or special purpose computer. Computer programmers in the art can easily reason codes and code segments, which constitute the computer program. The program is stored in a computer readable medium readable by the computer. When the program is read and run by a computer, the method of electing a leader node in an ad-hoc network is performed. Here, the computer-readable medium may be a magnetic recording medium, an optical recording medium, firmware, or other recordable media.

[0075] Although a few embodiments of the present invention have been shown and described, it would be appreciated by those skilled in the art that changes may be made in these embodiments without departing from the principles and spirit of the invention, the scope of which is defined in the claims and their equivalents.

Claims

Certificate of Correction present

The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.

What is claimed is:

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:

\sum_{K = 1}^{M} α_{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:

\sum_{K = 1}^{M} α_{K} * N_{K} \geq 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:

OP = \sum_{K = I}^{M} α_{K} * N_{K} 〉 T^{'}

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;

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:

\sum_{K = 1}^{M} α_{K} * N_{K}

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:

\sum_{K = 1}^{M} α_{K} * N_{K} \geq T

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:

OP = \sum_{K = 1}^{M} α_{K} * N_{K} 〉 T^{'}

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;

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.

Patent Citations (7)

Patent	Date	Inventor	Cited By
US6829222(B2)	2004-12-01	Amis et al.	Examiner
US2002/0018448(A1)	2002-02-01	Amis et al.	Examiner
US2003/0202465(A1)	2003-10-01	Cain	Examiner
US2003/0204625(A1)	2003-10-01	Cain	Examiner
US2005/0063313(A1)	2005-03-01	Nanavati et al.	Examiner
US2005/0132154(A1)	2005-06-01	Rao et al.	Examiner
US2006/0034193(A1)	2006-02-01	Shi et al.	Examiner

Non-Patent Literature (5)

Pardeep Parvathipuram, Vijay Kumar, Gi-Chul Yang, “An Efficient Leader Election Algorithm for Mobile Ad Hoc Networks”, Springer Berlin/Heidelberg, vol. 3347, 2004, pp. 32-41.Examiner
Sudarshan Vasudevan, Jim Kurose, Don Towsley, “Design and Analysis of a Leader Election Algorithm for Mobile Ad Hoc Networks”, UMass Computer Science Technical Report 3-20, 2004, Entire document.Examiner
P. Basu, N. Khan, T.D.C. Little, “ A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks”, MCL Technical Report No. 01-15-2001, 2001, Entire Document.Examiner
Kilian Weniger, Martina Zitterbart, “IPv6 Autoconfiguration in Large Scale Mobile Ad-Hoc Networks”, European Wireless 2002, vol. 1, Feb. 2002, pp. 144-147.Examiner
Navneet Malpani, Jennifer Welch, Nitin Vaidya, “Leader Election Algorithm for Mobile Ad Hoc Networks”, in Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communication, Boston 2000, pp. 96-103.Examiner

Abstract

Description

Cross-Reference to Related Application

Background of the Invention

[0002] 1. Field of the Invention

[0004] 2. Description of the Related Art

Summary of the Invention

[0017] An aspect of the present invention is to solve at least the above and/or other problems and disadvantages and to provide at least the advantages described below.

[0023]

\sum_{K = 1}^{M} α_{K} * N_{K}

[0024] According to an aspect of the present invention, the nodes that satisfy the following equation are determined as the candidate nodes:

[0025]

\sum_{K = 1}^{M} α_{K} * N_{K} \geq T

[0028] According to an aspect of the present invention, the method includes the leader node transmitting the leader election option message if it satisfies the following equation:

[0029]

OP = \sum_{K = I}^{M} α_{K} * N_{K} 〉 T^{'}

Brief Description of the Drawings

[0033] FIG. 1 is a flowchart illustrating a method of electing a leader node in an ad-hoc network according to an embodiment of the present invention;

[0034] FIG. 2 is a view illustrating an example of a neighbor node information list kept by a respective node in the ad-hoc network;

[0035] FIG. 3 is a view illustrating an example of a leader election option message according to an embodiment of the present invention;

[0036] FIG. 4A is a view illustrating an example of the ad-hoc network according to an embodiment of the present invention;

[0037] FIG. 4B is a view illustrating an example of a neighbor information list of a predetermined node of FIG. 4A;

[0038] FIG. 5 is flowchart illustrating a method of electing a new leader node when a leader node moves in the ad-hoc network according to an embodiment of the present invention; and

[0039] FIG. 6 is flowchart illustrating a method of electing a new leader node in accordance with the topology change of the ad-hoc network according to an embodiment of the present invention.

Detailed Description of the Embodiments

[0047]

\begin{matrix} P = \sum_{K = 1}^{M} α_{K} * N_{K} & [Equation 1] \end{matrix}

[0049] Each node that determined itself as the candidate leader transmits the leader election optional message to the whole network at operation S160.

[0067]

\begin{matrix} OP = \sum_{K = I}^{M} α_{K} * N_{K} & [Equation 2] \end{matrix}