Routing Method For Network And Sensing System

• US 20110055424A1
• Filed: 01/20/2010
• Published: 03/03/2011
• Est. Priority Date: 09/01/2009
• Status: Active Grant

• Current Assignee: National Taiwan University (Government of The Republic of China)
• Original Assignee: National Taiwan University (Government of The Republic of China)
• Inventors: Liao, Kuo-Chi, Yang, En-Cheng, Jiang, Joe-Air, Tseng, Chwan-Lu, Lu, Fu-Ming, Chen, Chia-Pang, Lin, Tzu-Shiang, Shieh, Jyh-Cherng, Chuang, Cheng-Long
• Granted Patent: US 8,549,174 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 4/12 Messaging; Mailboxes; Announcements
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• 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 routing method for a network is provided. The routing method includes the steps of a) selecting one of a plurality of basic nodes as a cluster head; b) broadcasting a first message by the cluster head; c) continuing to broadcast the first message by any of the plurality of basic nodes which receives the first message, until all the plurality of basic nodes receive the first message; and d) selecting a corresponding father node by each of the plurality of basic nodes based on an information associated with the first message.

Claims

1. A routing method for a network, comprising steps of:

a) selecting one of a plurality of basic nodes as a cluster head;

b) broadcasting a first message by the cluster head;

c) continuing to broadcast the first message by any of the plurality of basic nodes which receives the first message, until all the plurality of basic nodes receive the first message; and

d) selecting a corresponding father node by each of the plurality of basic nodes based on an information associated with the first message.

2. A method according to claim 1, wherein:

the step a) further comprises a substep of calculating a first weighting value to select the cluster head based on;

a residual electric power in the each basic node;

a ratio of an overlapping area between a covering area of the each basic node and a covering area of other basic node(s) of the plurality of basic nodes to the covering area of the each basic node; and

a distance between the each basic node and a base station, wherein the covering area is a sensing area of the each basic node, and the sensing area includes one of a quantity of at least an interested spot to be sensed and an area to be sensed; and

the step d) further comprises substeps of grouping the plurality of basic nodes into a plurality of basic node sets, and selecting a specific basic node of a specific basic node set to serve as a father node of the specific node set to which the each basic node belongs.

3. A method according to claim 1, further comprising steps of:

e) through the each basic node transmitting the first message and a sensing message collected by the each basic node to the corresponding father node;

f) receiving the first message and the sensing message from the corresponding father node by the cluster head; and

g) transmitting the first message and the sensing message to a base station by the cluster head, wherein the network is a wireless sensor network.

4. A method according to claim 3, further comprising a step of:

h) repeating the steps a) to g) when at least one of the plurality of basic nodes still has an available electric power.

5. A method according to claim 3, wherein the first message comprises at least one selected from a group consisting of codes of the each basic node and the cluster head, residual electric quantities of the each basic node and the cluster head, hierarchical levels of the each basic node and the cluster head, a distance between the each basic node and one of the plurality of basic nodes adjacent to the each basic node, a distance between the cluster head and one of the plurality of basic nodes adjacent to the clustering head, and the sensing message comprises at least one of an environmental message and an environmental changing condition within a sensing area of the each basic node.

6. A method according to claim 5, wherein the sensing message comprises one selected from a group consisting of a parameter, an image message, an audio message, and a combination thereof.

7. A method according to claim 1, wherein the step d) further comprises a substep of calculating a second weighting value to select the corresponding father node based on a distance between the basic each node and another one of the plurality of basic nodes, and a residual electric power of the another basic node.

8. A sensing system, comprising:

a plurality of basic nodes;

a plurality of father nodes, each of which is selected from the plurality of basic nodes, corresponds to at least one of the plurality of basic nodes, and receives a first message from the corresponding basic node;

a cluster head receiving the first message from the plurality of father nodes; and

a base station receiving the first message from the cluster head.

9. A system according to claim 8, being a wireless sensor network system, and using a multi-hop routing algorithm including a calculation of plural rounds to select the cluster head based on a first maximum weighting value, and to select the plurality of father nodes based on a second maximum weighting value.

10. A system according to claim 9, wherein the first maximum weighting value is calculated to select the cluster head based on:

a residual electric power in each of the plurality of basic nodes;

a ratio of an overlapping area between a covering area of the each basic node and a covering area of other basic node(s) of the plurality of basic nodes to the covering area of the each basic node; and

a distance between the each basic node and the base station,

wherein the covering area is a sensing area of the each basic node, and the sensing area includes one of a quantity of at least an interested spot to be sensed and an area to be sensed.

11. A system according to claim 9, wherein each of the plurality of basic nodes corresponds to at least a candidate node for transmitting the first message, and the second maximum weighting value is calculated based on a residual electric power of the candidate node and a respective distance between the candidate node and the each basic node so as to select one of the candidate node as the father node for the each basic node.

12. A system according to claim 9, wherein when one of the plural rounds in the multi-hop routing algorithm is completed, and at least one of the plurality of basic nodes still has an available electric power, then another one of the plural rounds proceeds.

13. A system according to claim 8, wherein the first message comprises at least one selected from a group consisting of codes of each of the plurality of basic nodes and the clustering head, residual electric quantities of the each basic node and the clustering head, hierarchical levels of the each basic node and the clustering head, a distance between the each basic node and one of the plurality of basic nodes adjacent to the each basic node, a distance between the cluster head and one of the plurality of basic nodes adjacent to the cluster head, and a sensing message including at least one of an environmental message and an environmental changing condition within a sensing area of the each basic node.

14. A system according to claim 13, wherein the sensing message comprises one selected from a group consisting of a parameter, an image message, an audio message and a combination thereof.

15. A routing method for a network, comprising steps of:

a) selecting one of a plurality of basic nodes as a cluster head;

b) building a plurality of hierarchical levels for the plurality of basic nodes based on an information associated with the cluster head; and

c) sequentially transmitting a first message by the plurality of basic nodes according to the hierarchical levels.

16. A method according to claim 15, further comprising steps of:

d) receiving the first message by the cluster head; and

e) transmitting the first message to a base station by the cluster head.

17. A method according to claim 16, further comprising a step of:

f) repeating the steps a) to e) when at least one of the plurality of basic nodes still has an available electric power.

18. A method according to claim 15, wherein the step a) further comprises a substep of calculating a first weighting value to select the cluster head based on:

a residual electric power in each of the plurality of basic nodes;

a ratio of an overlapping area between a covering area of the each basic node and a covering area of other basic node(s) of the plurality of basic nodes to the covering area of the each basic node; and

a distance between the each basic node and the base station,

wherein the covering area is a sensing area of the each basic node, and the sensing area includes one of a quantity of at least an interested spot to be sensed and an area to be sensed.

19. A method according to claim 15, wherein each of the plurality of basic nodes corresponds to at least a candidate node for transmitting the first message, the step b) further comprises a substep of building the plurality of hierarchical levels based on a respective distance between the each basic node and the cluster head, and the step c) further comprises a substep of calculating a second weighting value based on a residual electric power of the candidate node and a respective distance between the candidate node and the each basic node to determine which candidate node in each of the hierarchical levels is to receive the first message.

20. A method according to claim 15, wherein the first message comprises at least one selected from a group consisting of codes of each of the plurality of basic nodes and the cluster head, residual electric quantities of the each basic node and the cluster head, the hierarchical levels of the each basic node and the cluster head, a distance between the each basic node and one of the plurality of basic nodes adjacent to the each basic node, a distance between the cluster head and one of the plurality of basic nodes adjacent to the cluster head, and a sensing message including at least one of an environmental message and an environmental changing condition within a sensing area of the each node.