WIRELESS SENSOR NETWORK AND SAMPLING RATE ALLOCATION METHOD THEREOF

• US 20090251297A1
• Filed: 10/14/2008
• Published: 10/08/2009
• Est. Priority Date: 04/08/2008
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Shen, Chung-Chou, Huang, Tai-Yi, Yu, Huang-Yi, Chiang, Po-Nung, Chu, Tsung-Hsien
• Granted Patent: US 8,085,134 B2
• Time in Patent Office: Days
• US Class Current: 340/286.20
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 52/0251 using monitoring of local events, e.g. events related to user activity
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A sampling rate allocation method for a wireless sensor network is provided. In this method, a distributed computing method is adopted to allow each node to calculate and obtain its decision table and energy table and upload its energy table to its parent node, and finally, the number of samples to be provided by all the child nodes is determined according to the decision table of the root node and a total sample number. Compared to the conventional techniques, the present invention provides a wireless sensor network which has longer life time and can meet the requirements to both the total number of samples and the fairness.

Claims

1. A wireless sensor network, comprising:

a root node, for sending a total sample number to at least one internal node and a plurality of leaf nodes, wherein the total number of samples is the number of samples to be sensed by the wireless sensor network within a specific time;

the leaf nodes, wherein each of the leaf nodes calculates the remaining energy after providing a sample and generates a first calculation result, and the leaf node uploads the first calculation result to the internal node; and

the internal node, wherein the internal node generates a second calculation result and a third calculation result based on the first calculation results and uploads the second calculation result to the root node;

wherein the root node generates a fourth calculation result and a fifth calculation result based on the second calculation result, then the root node determines the number of samples to be sent by the internal node to the root node within the specific time according to the fifth calculation result and the total number of samples, and finally, the internal node determines the number of samples to be sensed by the internal node and the leaf nodes within the specific time according to the number of samples to be sent by the internal node to the root node and the third calculation result.

2. The wireless sensor network according to claim 1, wherein the first calculation results are energy tables of the leaf nodes, the second calculation result and the third calculation result are respectively an energy table and a decision table of the internal node, and the fourth calculation result and the fifth calculation result are respectively an energy table and a decision table of the root node.

3. The wireless sensor network according to claim 2, wherein the internal node calculates a temporary decision table and a temporary energy table according to the energy tables of the leaf nodes and then corrects the temporary decision table and the temporary energy table according to whether the internal node can automatically sense samples so as to generate the decision table and the energy table of the internal node, the decision table of the internal node records the mapping between the number of samples to be uploaded by the internal node to the root node within the specific time and the number of samples to be sensed by the internal node and the leaf nodes, and the decision table of the root node records the mapping between the total number of samples and the number of samples to be provided by the internal node to the root node.

4. The wireless sensor network according to claim 2, wherein the root node further sends a maximum sampling rate and a minimum sampling rate of the internal node and a maximum sampling rate and a minimum sampling rate of each of the leaf nodes, the number of samples to be sensed by the internal node within the specific time has to be between the maximum sampling rate and the minimum sampling rate of the internal node, and the number of samples to be sensed by each of the leaf nodes within the specific time has to be between the maximum sampling rate and the minimum sampling rate of the leaf node.

5. The wireless sensor network according to claim 4, wherein the maximum sampling rate and the minimum sampling rate of the internal node and the maximum sampling rate and the minimum sampling rate of each of the leaf nodes are determined through a minimum mean deviation method or a weighting method.

6. A wireless sensor network, comprising:

a root node, for sending a total sample number to a plurality of leaf nodes, wherein the total number of samples is the number of samples to be sensed by the wireless sensor network within a specific time; and

the leaf nodes, wherein each of the leaf nodes calculates the remaining energy after providing a sample and generates a first calculation result, and the leaf node uploads the first calculation result to the root node;

wherein the root node generates a second calculation result and a third calculation result based on the first calculation results, and then the root node determines the number of samples to be sensed by the leaf nodes within the specific time according to the third calculation result and the total number of samples.

7. The wireless sensor network according to claim 6, wherein the first calculation results are energy tables of the leaf nodes, and the second calculation result and the third calculation result are respectively an energy table and a decision table of the root node.

8. The wireless sensor network according to claim 7, wherein the decision table of the root node records the mapping between the total number of samples and the number of samples to be sensed by the leaf nodes.

9. The wireless sensor network according to claim 7, wherein the root node further sends a maximum sampling rate and a minimum sampling rate of each of the leaf nodes, and the number of samples to be sensed by each of the leaf nodes within the specific time has to be between the maximum sampling rate and the minimum sampling rate of the leaf node.

10. The wireless sensor network according to claim 9, wherein the maximum sampling rate and the minimum sampling rate of each of the leaf nodes are determined through a minimum mean deviation method or a weighting method.

11. A sampling rate allocation method, suitable for a wireless sensor network in tree topology, wherein the wireless sensor network comprises a root node and a plurality of leaf nodes, the sampling rate allocation method comprising:

sending a total sample number to each of the leaf nodes by using the root node, wherein the total number of samples is the number of samples to be sensed by the wireless sensor network within a specific time;

calculating the remaining energy of each of the leaf nodes after the leaf node provides a sample, generating a first calculation result, and uploading the first calculation result to the root node by using the leaf node;

generating a second calculation result and a third calculation result based on the first calculation results by using the root node; and

determining the number of samples to be sensed by the leaf nodes within the specific time according to the third calculation result and the total number of samples by using the root node.

12. The sampling rate allocation method according to claim 11, wherein the first calculation results are energy tables of the leaf nodes, the second calculation result and the third calculation result are respectively an energy table and a decision table of the root node, and the decision table of the root node records the mapping between the total number of samples and the number of samples to be sensed by the leaf nodes.

13. The sampling rate allocation method according to claim 12, wherein the process executed by each of the leaf nodes comprises:

determining whether a total sample number R is received from the root node S₀ by using the leaf node S_i, wherein if the total number of samples R is not received, the leaf node S_i waits until the total number of samples R is received from the root node S₀;

beginning to calculate and establish an energy table E_i of the leaf node S_i by using the leaf node S_i, wherein the energy table E_i has R+1 rows, each of the rows has a field, the field of the 0^th row represents the original energy of the leaf node S_i, and the field E_i[j] of the j^th row (j>

0) represents the remaining energy after the leaf node S_i provides a j^th sample;

sending the energy table E_i to the root node S₀ by using the leaf node S_i after the fields of all the rows in the energy table E_i are calculated; and

determining whether the root node S₀ designates a number x_i of samples to be sensed by the leaf nodes within the specific time by using the leaf node S_i, wherein if the root node S₀ designates the number x_i, the leaf node S_i senses and captures samples according to the number x_i designated by the root node S₀;

otherwise, the leaf node S_i waits until the root node S₀ designates the number x_i.

14. The sampling rate allocation method according to claim 12, wherein the process executed by the root node comprises:

determining whether the energy tables sent by the leaf nodes are received by using the root node S₀, wherein if the root node S₀ does not receive the energy tables, the root node S₀ waits until the energy tables sent by the leaf nodes are received;

determining a source node of each sample until the R^th sample by using the root node S₀, wherein the root node S₀ selects the leaf node S_i having the most remaining energy after the sample is provided as the source node of the sample, δ

_i represents the number of samples already provided by the leaf node S_i, δ

_i is increased by 1 whenever the leaf node S_i provides a sample, δ

_i=0 when the leaf node S_i provides no sample yet, wherein i=1˜

y, then the values in the 0^th row of the decision table D₀ of the root node S₀ are all 0, the root node S₀ selects the source node of the m^th sample based on max{E₁[δ

₁+1],E₂[δ

₂+1],E₃[δ

₃+1], . . . ,E_y[δ

_y+1]}, if the leaf node S_j is selected, then δ

_j=δ

_j+1, the other δ

_i having i≠

j are not changed, the m^th row of the decision table D₀ of the root node S₀ are respectively filled with each δ

_k, k=1,2, . . . ,y, namely, D₀[m,k]=δ

_k, and the critical energy is E₀[m]=min{E₁[δ

₁],E₂[δ

₂],E₃[δ

₃], . . . ,E_y[δ

_y]}; and

allocating the number of samples to be sensed by the leaf node S_i within the specific time according to the R^th row in the decision table D₀ by using the root node S₀.

15. The sampling rate allocation method according to claim 12, wherein the root node further sends a maximum sampling rate and a minimum sampling rate of each of the leaf nodes, and the number of samples to be sensed by each of the leaf nodes within the specific time has to be between the maximum sampling rate and the minimum sampling rate of the leaf node.

16. The sampling rate allocation method according to claim 15, wherein the process executed by the root node comprises:

determining whether the energy tables sent by the leaf nodes are received by using the root node S₀, wherein if the root node S₀ does not receive the energy tables, the root node S₀ waits until the energy tables sent by the leaf nodes are received;

determining a source node of each sample starting from the

17. The sampling rate allocation method according to claim 16, wherein the maximum sampling rate and the minimum sampling rate of each of the leaf nodes are determined through a minimum mean deviation method or a weighting method.

18. A sampling rate allocation method, suitable for a wireless sensor network in tree topology, wherein the wireless sensor network comprises a root node, at least one internal node, and a plurality of leaf nodes, the sampling rate allocation method comprising:

sending a total sample number to the internal node and each of the leaf nodes by using the root node, wherein the total number of samples is the number of samples to be sensed by the wireless sensor network within a specific time;

calculating the remaining energy of each of the leaf nodes after the leaf node provides a sample, generating a first calculation result, and uploading the first calculation result to the internal node by using each of the leaf nodes;

generating a second calculation result and a third calculation result based on the first calculation results and uploading the second calculation result and the third calculation result to the root node by using the internal node;

generating a fourth calculation result and a fifth calculation result based on the second calculation result by using the root node;

determining the number of samples to be sent by the internal node to the root node within the specific time according to the fifth calculation result and the total number of samples by using the root node; and

determining the number of samples to be sensed by the internal node and the leaf nodes within the specific time according to the number of samples to be sent by the internal node to the root node and the third calculation result by using the internal node.

19. The sampling rate allocation method according to claim 18, wherein the first calculation results are energy tables of the leaf nodes, the second calculation result and the third calculation result are respectively an energy table and a decision table of the internal node, and the fourth calculation result and the fifth calculation result are respectively an energy table and a decision table of the root node, wherein the decision table of the root node records the mapping between the total number of samples and the number of samples to be provided by the internal node to the root node, and the decision table of the internal node records the mapping between the number of samples to be uploaded by the internal node to the root node within the specific time and the number of samples to be sensed by the internal node and the leaf nodes.

20. The sampling rate allocation method according to claim 19, wherein the process executed by each of the leaf nodes comprises:

determining whether the total number of samples R is received from the root node S₀ by using the leaf node S_i, wherein if the total number of samples R is not received, the leaf node S_i waits until the total number of samples R is received from the root node S₀;

beginning to calculate and establish an energy table E_i by using the leaf node S_i, wherein the energy table E_i has R+1 rows, each of the rows has a field, the field of the 0^th row represents the original energy of the leaf node S_i, and the field E_i[j] of the j^th row (j>

0) represents the remaining energy after a j^th sample is provided;

sending the energy table E_i to the internal node S_k by using the leaf node S_i after the fields of all the rows in the energy table E_i are calculated; and

determining whether the internal node S_k designates the number x_i of samples to be sensed by the leaf nodes within the specific time by using leaf node S_i, wherein if the internal node S_k designates the number x_i, the leaf node S_i senses and obtains samples according to the number x_i designated by the internal node S_k;

otherwise, the leaf node S_i waits until the internal node S_k designates the number x_i.

21. The sampling rate allocation method according to claim 20, wherein the process executed by the internal node S_k comprises:

determining whether the energy tables sent by all the leaf nodes are received by using the internal node S_k, wherein if the energy tables are not received, the internal node S_k waits until the energy tables of all the leaf nodes are received;

determining a source node for each sample until the R^th sample by using the internal node S_k, wherein the internal node S_k selects the leaf node having the most remaining energy after the sample is provided as the source node of the sample, δ

_i represents the number of sample already provided by the leaf node S_i, δ

_i is increased by 1 whenever the leaf node S_i provides a sample, δ

_i=0 when the leaf node S_i provides no sample yet, wherein i=1˜

y, then the values in the 0^th row of the decision table D_k of the internal node S_k are all 0, the internal node S_k determines the source node of the m^th sample based on max{E₁[δ

₁+1],E₂[δ

₂+1],E₃[δ

₃+1], . . . ,E_y[δ

_y+1]}, if the leaf node S_j is selected, then δ

_j=δ

_j+1, the other δ

_i having i≠

j are not changed, the m^th row of the decision table D_k of the root node are respectively filled with each δ

_i, i=1,2, . . . ,y, namely, D_k[m,i]=δ

_i, and the critical energy is E_k[m]=min{E₁[δ

₁],E₂[δ

₂],E₃[δ

₃], . . . ,E_y[δ

_y]};

determining whether the internal node S_k can take samples and accordingly correcting the energy table E_k or the decision table D_k of the root node by using the internal node S_k; and

uploading the energy table E_k and the decision table D_k to the root node S₀ by using the internal node S_k;

determining whether the number of samples to be provided by the internal node S_k to the root node S₀ in the specific time is received by using the internal node S_k, wherein if the samples are not received, the internal node S_k waits until the number of samples to be provided by the internal node S_k to the root node S₀ in the specific time is received; and

allocating the number of samples to be sensed by the leaf node S_i and the internal node S_k within the specific time by according to the u^th row in the decision table D_k by using the internal node S_k, wherein u is the number of samples allocated by the root node to the internal node S_k.

22. The sampling rate allocation method according to claim 21, wherein the process executed by the root node comprises:

determining whether the energy table sent by the internal node S_k is received by using the root node S₀, wherein if the energy table sent by the internal node S_k is not received, the root node S₀ waits until the energy table sent by the internal node S_k is received;

determining a source node for each sample until the R^th sample by using the root node S₀, wherein the root node S₀ selects the internal node S_k having the most remaining energy after the sample is provided as the source node of the sample, δ

_k represents the number of samples already provided by the internal node S_k, δ

_k is increased by 1 whenever the internal node S_k provides a sample, δ

_k=0 when the internal node S_k provides no sample yet, wherein k=1˜

y, then the values in the 0^th row of the decision table D₀ of the root node S₀ are all 0, the root node S₀ determines the source node of the m^th sample based on max{E₁[(δ

₁+1],E₂[δ

₂+1],E₃[δ

₃+1], . . . ,E_y[δ

_y+1]}, if the internal node S_x is selected, then δ

_x=δ

_x+1, the other δ

_k having k≠

x are not changed, the m^th row in the decision table D₀ of the root node S₀ are respectively filled with each δ

_k, k=1,2, . . . ,y, namely, D₀[m,k]=δ

_k, and the critical energy is E₀[m]=min{E₁[δ

₁],E₂[δ

₂],E₃[δ

₃], . . . ,E_y[δ

_y]}; and

allocating the number of samples to be provided by the internal node S_k to the root node S₀ within the specific time according to the R^th row in the decision table D₀ by using the root node S₀.

23. The sampling rate allocation method according to claim 22, wherein the step of determining whether the internal node S_k can take samples and accordingly correcting the energy table E_k or the decision table D_k of the internal node S_k by using the internal node S_k comprises:

using a virtual node S_c to represent all the leaf nodes, the energy table E_c of the virtual node S_c is the energy table E_k of the internal node S_k, the decision table D_c of the virtual node S_c is the energy table E_k of the internal node S_k;

determining whether each sample should be sensed by the internal node S_k or provided by the virtual node S_c by using the internal node S_k if the internal node S_k can take samples, wherein when m samples are provided, the internal node S_k providing 0 sample and the virtual node S_c providing m samples until the internal node S_k providing m samples and the virtual node S_c providing 0 sample have to be checked, and a combination which allows the critical energy to have the maximum value is selected, and the decision table D_k and the energy table E_k are then corrected according to the energy of the internal node S_k; and

setting the 0^th field in each row of the decision table D_k as 0 and correcting the energy table E_k according to the energy of the internal node S_k if the internal node S_k cannot sense and obtain samples.

24. The sampling rate allocation method according to claim 19, wherein the root node further sends a maximum sampling rate and a minimum sampling rate of the internal node and a maximum sampling rate and a minimum sampling rate of each of the leaf nodes, the number of samples to be sensed by the internal node within the specific time has to be between the maximum sampling rate and the minimum sampling rate of the internal node, and the number of samples to be sensed by each of the leaf nodes within the specific time has to be between the maximum sampling rate and the minimum sampling rate of the leaf node.

25. The sampling rate allocation method according to claim 24, wherein the process executed by the internal node comprises:

determining whether the energy tables sent by all the leaf nodes are received by using the internal node S_k, wherein if the energy tables are not received, the internal node S_k waits until all the energy tables sent by all of the leaf nodes are received;

determining a source node for each sample starting from the

26. The sampling rate allocation method according to claim 25, wherein the process executed by the root node comprises:

determining whether the energy table sent by the internal node S_k is received by using the root node S₀, wherein if the energy table is not received, the root node S₀ waits until the energy table sent by the internal node S_k is received;

determining a source node for each sample from the

27. The sampling rate allocation method according to claim 24, wherein the maximum sampling rate and the minimum sampling rate of the internal node and the maximum sampling rate and the minimum sampling of each of the leaf nodes are determined through a minimum mean deviation method or a weighting method.