Path selection apparatus, path selection method and program

Abstract

A path selection apparatus in a sensor tree includes a node moving unit that selects a first node in the sensor tree, and moves a second node to under a third node in the sensor tree if the total number of packets transmitted and received in the sensor tree is reduced as a result of the second node being moved to under the third node, the first node having a child node under the first node, the second node being located under a subtree of which a vertex is the first node, the third node not belonging to the subtree. If nodes under the subtree of which the vertex is the first node do not include anode that reduces the total number of packets as a result of being moved, the node moving unit moves a node that is included in the nodes under the subtree and does not change the total number of packets, to under the third node.

Claims

1. A path selection apparatus for selecting a path along which sensor reports stored in packets are transmitted from lower nodes to upper nodes in a sensor tree that is constituted by a plurality of nodes including a plurality of sensor nodes, the path selection apparatus comprising: a processor; a memory device storing a program that causes the processor to select a first node in the sensor tree, move a second node to under a third node in the sensor tree if a total number of packets transmitted and received in the sensor tree is reduced as a result of the second node being moved to under the third node, the first node having a child node under the first node, the second node being located under a subtree of which a vertex is the first node, the third node not belonging to the subtree, and if nodes under the subtree of which the vertex is the first node do not include a node that reduces the total number of packets as a result of being moved, determine whether the nodes under the subtree includes a node that meets a condition, said condition including moving the node does not change the total number of packets, and move the node to under the third node upon determining that the node meets the condition.

2. The path selection apparatus according to claim 1, wherein the processor determines a change in the total number of packets as a result of movement of a node, with respect to each node under the subtree of which the vertex is the first node, and moves a node that most reduces the total number of packets.

3. The path selection apparatus according to claim 1, wherein if nodes are repeatedly moved in the sensor tree, the processor sets an upper limit of the number of times each node is selected as a vertex node of a subtree.

4. The path selection apparatus according to claim 3, wherein if nodes are repeatedly moved in the sensor tree, the processor sets an upper limit of the number of times each node is moved and an upper limit of the number of times a node that does not change the total number of packets is moved.

5. The path selection apparatus according to claim 1, wherein if nodes are repeatedly moved in the sensor tree, the processor sets an upper limit of the number of times each node is moved.

6. The path selection apparatus according to claim 1, wherein if nodes are repeatedly moved in the sensor tree, the processor sets an upper limit of the number of times a node that does not change the total number of packets is moved.

7. A non-transitory computer-readable recording medium storing a program for causing a computer to function as the path selection apparatus according to claim 1.

8. The path selection apparatus according to claim 1, wherein the processor examines all of the nodes under the subtree of which the vertex is the first node and determines whether any one of the nodes under the subtree reduces the total number of packets as a result of being moved before determining whether the nodes under the subtree includes the node that meets the condition.

9. A path selection method performed in a path selection apparatus for selecting a path along which sensor reports stored in packets are transmitted from lower nodes to upper nodes in a sensor tree that is constituted by a plurality of nodes including a plurality of sensor nodes, the path selection method comprising: selecting a first node in the sensor tree; moving a second node to under a third node in the sensor tree if a total number of packets transmitted and received in the sensor tree is reduced as a result of the second node being moved to under the third node, the first node having a child node under the first node, the second node being located under a subtree of which a vertex is the first node, the third node not belonging to the subtree; and if nodes under the subtree of which the vertex is the first node do not include a node that reduces the total number of packets as a result of being moved, determining whether the nodes under the subtree includes a node that meets a condition, said condition including moving the node does not change the total number of packets, and moving the node to under the third node upon determining that the node meets the condition.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a diagram showing an example of the numbers of packets with respect to links on a data collection tree.

(2) FIG. 2 is a diagram showing shortest path trees applied to the MECAT problem.

(3) FIG. 3 is a diagram showing an example (example 1) of application of the (3, 2)—LAST algorithm to the MECAT-RN problem.

(4) FIG. 4 is a diagram showing an example (example 2) of application of the (3,2)—LAST algorithm to the MECAT-RN problem.

(5) FIG. 5 is a flowchart showing a method for creating a tree in a conventional method.

(6) FIG. 6 is a diagram showing a problem that occurs in a conventional method.

(7) FIG. 7 is a diagram showing an ideal movement result for minimizing the number of packets.

(8) FIG. 8 is a diagram showing an example in which the number of packets is reduced by k when compared to a conventional method.

(9) FIG. 9 is a diagram showing an example of a functional configuration of a path selection apparatus in an embodiment of the present invention.

(10) FIG. 10 is a flowchart showing operation of the path selection apparatus in an embodiment of the present invention.

(11) FIG. 11 shows an example of movement of nodes when an embodiment of the present invention is applied to the MECAT problem.

(12) FIG. 12 shows an example of movement of nodes when an embodiment of the present invention is applied to the MECAT-RN problem.

(13) FIG. 13 is a diagram showing an effect of reducing the number of packets relative to that in a conventional method.

(14) FIG. 14 is a diagram showing increase in the total number of times of movement relative to that in a conventional method.

(15) FIG. 15 is a diagram showing a result of comparison with a conventional method regarding the total movement time.

(16) FIG. 16 is a diagram showing an example of a hardware configuration of the path selection apparatus in an embodiment of the present invention.

DESCRIPTION OF EMBODIMENTS

(17) The following describes an embodiment of the present invention based on Figures. FIG. 9 shows an example of a functional configuration of a path selection apparatus 100 in an embodiment of the present invention.

(18) In the present embodiment, a manner of use of a network is assumed in which data collection cycles are repeated in a sensor tree that is constituted by a plurality of nodes (sensor nodes/relay nodes) by transmitting sensor reports stored in packets from lower nodes to upper nodes. The present embodiment can be applied to both a WSN that does not include relay nodes and a WSN that includes relay nodes.

(19) As can be understood from the example shown in FIG. 1, the number of reports transmitted from each node varies between nodes, and energy can be saved by reducing the hop count from a node that has a large number of reports to the root node as far as possible. Also, if the remainder (d(below_i)+d(i)) % S is not zero, there is room in a transmitted and received packet, and therefore, energy can be saved by filling each packet with the maximum number S of sensor reports as far as possible. From these standpoints, the path selection apparatus 100 moves nodes on a sensor tree and selects a path with which the energy consumption can be reduced.

(20) As shown in FIG. 5, the path selection apparatus 100 is constituted by a node information acquisition unit 110, a routing requesting unit 120, a route determination unit 130, a WSN storing unit 140, and a tree storing unit 150. The route determination unit 130 includes a WSN recognition unit 131, an initial tree creation unit 132, a sensor report number calculation unit 133, and a node moving unit 134. In this example, the path selection apparatus 100 is included in a root node (0), but the path selection apparatus 100 does not necessarily have to be included in the root node, and may also be included in an apparatus, such as a base station, that is connected to the root node, for example.

(21) The node information acquisition unit 110 acquires information regarding nodes that are adjacent to the root node, and acquires information regarding nodes that are adjacent to those nodes. Acquisition of information regarding nodes is repeated in a similar manner, and as a result, adjacency relationships between all nodes that belong to a WSN to which the root node belongs can be acquired.

(22) The WSN recognition unit 131 in the route determination unit 130 can recognize the configuration of the WSN based on the adjacency relationships between the nodes, and as a result, stores the configuration of the WSN in the WSN storing unit 140.

(23) The initial tree creation unit 132 creates an initial tree. In order to create the initial tree, it is possible to consider using a shortest path tree in the MECAT problem and the (3, 2)—LAST algorithm in the MECAT-RN problem, for example. The thus created initial tree is stored in the tree storing unit 150.

(24) The sensor report number calculation unit 133 sets the number d(i) of sensor reports for each node i on the initial tree, and determines the total number d(below_i) of sensor reports from lower nodes that the node i transfers.

(25) The node moving unit 134 repeatedly moves nodes on the sensor tree so that the total number of packets transmitted and received on the sensor tree will be finally reduced. The node moving unit 134 stores a tree that is obtained by moving nodes, in the tree storing unit 150.

(26) The configuration of a finally created tree is reflected to a tree on the actual WSN as a result of the routing requesting unit 120 performing setting of routing with respect to each node.

(27) Next, a flowchart shown in FIG. 10 will be described. FIG. 10 is a flowchart showing operation of the path selection apparatus 100 in an embodiment of the present invention.

(28) STEP 101 is initially a step in which the initial tree creation unit 132 creates an initial tree. The initial tree is created using an existing method, such as the shortest path tree in the MECAT problem or the (3, 2)—LAST in the MECAT-RN. Thereafter, if it is determined to move one node from a subtree to another subtree in STEP 104 and STEP 105, which will be described below, STEP 101 is a step in which the node moving unit 134 creates a tree that is obtained by moving the node. With respect to each node i on the initial tree, the sensor report number calculation unit 133 sets the number d(i) of reports created by the node i and the total number d(below_i) of sensor reports from lower nodes that the node i transfers. Also, if there is a change in the total number d (below_i) of sensor reports from lower nodes that the node i transfers in a tree obtained by moving a node, the sensor report number calculation unit again sets d(below_i).

(29) The following STEP 102 to STEP 105 are steps that are executed by the node moving unit 134.

(30) In STEP 102, a vertex node of a movement target subtree is determined in the tree created in STEP 101. Conditions for the determination are that the vertex node is not a leaf node on the tree and has at least one child node. Also, a node that has not yet been selected in a loop between STEP 102 and STEP 105 after an interim tree has been created in STEP 101 is selected. However, if the number of times a node has already been selected as a vertex node of a subtree has reached the maximum number of times the node can be selected as a vertex node of a subtree, the node will not be selected as a vertex node of a subtree more than the maximum number of times.

(31) In STEP 103, whether or not a vertex node of a subtree can be selected in STEP 102 is determined. If a vertex node cannot be selected (No), a tree that has been created by that point in time is taken to be a final output tree, and the processing ends. If a vertex node of a subtree can be selected, the routine proceeds to processing in STEP 4.

(32) In STEP 104, it is determined whether or not nodes (except the vertex node) under the vertex node of the subtree include a node that reduces the total number of packets transmitted and received on the tree, as a result of the node being moved. A condition for the determination is that a parent node of the destination of the movement does not belong to the subtree. Here, a node that most reduces the number of packets as a result of being moved is moved to under a node other than the subtree, to increase an effect of reducing the energy consumption. However, if examination of all nodes under the subtree revealed that the number of packets cannot be reduced by moving any of the nodes under the subtree, a node that does not change the number of packets even if the node is moved is moved. However, a node that has already been moved the maximum number of times will not be moved.

(33) If it is determined in STEP 104 that there is a node that can be moved (Yes), the routine proceeds from STEP 105 to processing in STEP 101, and the node is moved to under a movement destination node to create a post-movement tree. If it is determined that there is no node that can be moved under the subtree (No), the routine proceeds to STEP 102 and a vertex node of another subtree is searched for.

(34) Note that the upper limit of the number of times of movement referred to in STEP 104 may be the upper limit of the number of times of movement for a node that does not change the total number of packets even if the node is moved. Either of the upper limit of the number of times of movement referred to in STEP 104 and the upper limit of the number of times each node can be selected as a vertex node of a subtree, which is referred to in STEP 102, is necessary in the present embodiment. This is because unless either of these restrictions is imposed, movement of a node that does not change the total number of packets may be looped (movement of the node between two parent nodes may be infinitely repeated), and in such a case, the flowchart shown in FIG. 10 will not end.

(35) <Example of Application to MECAT Problem>

(36) FIG. 11 shows an example of movement of nodes when the present embodiment is applied to the MECAT problem. In this example, a shortest path tree is already created as shown in (1) in FIG. 11. In FIG. 11, “a” shown in parentheses such as (a) in each tree node indicates the number d(i) of sensor reports created by a node i in one data collection cycle, and underlined “b” shown beside (a) indicates the total number d(below_i) of sensor reports from all lower nodes that the node i transfers. Solid line arrows show adjacency relationships between tree nodes, and sensor reports are transferred from lower nodes to upper nodes along the solid lines, and finally transmitted to a root node 0. Dotted lines show adjacency relationships between nodes, which are not used in the tree. A numeral shown beside each link indicates the number of packets transmitted on the link, and the data aggregation rate S is five.

(37) On the shortest path tree of this example shown in (1) in FIG. 11, which is an initial tree, N11, N12, N13, N22, and. N31 are nodes that have child nodes, and accordingly, one of these nodes is selected as a vertex node of a subtree. In this example, even if N31 is selected as a vertex node of a subtree, no node under N31 can be moved. This is because N41 under N31 does not have an adjacency relationship other than a link on the tree.

(38) If N11 is selected as a vertex of a subtree, moving N21 to under N31 is considered in STEP 104 in FIG. 10. In this case, the number of packets is increased by one on each of the links between N31 and N22, N22 and N12, and N12 and 0, while the number of packets is reduced by two between N11 and 0. Accordingly, the total number of packets is increased by one. If the number of packets is increased as described above, the node is not moved. If N13 is selected as a vertex of a subtree, the number of packets is increased by one as a result of N23 being moved to under N32, and therefore the node is not moved.

(39) If N12 or N22 is selected as a vertex of a subtree, N31 and N32 under these nodes are considered as targets of movement. This is because N31 has an adjacency relationship with N21 and N32 has an adjacency relationship with N23. Although the number of packets does not change as a result of either of N31 and N32 being moved, it is determined that N31 and N32 can be moved, in STEP 104 in FIG. 10. In this case, either of these nodes is moved, and in (2) in FIG. 11 of this example, it is assumed that N32 has been moved.

(40) Here, a vertex node of a subtree in the post-movement tree shown in (2) in FIG. 11 is selected by returning to STEP 101 in FIG. 10 again. Here, if N13 or N23 is selected by chance, N32 returns to under N22, but if N12 or N22 is selected, N31 moves from under N22 to under N21. This is because as a result of this movement, the number of packets is reduced by one on each of the links between N22 and N12, and N12 and 0, and consequently the total number of packets is reduced by two, as shown in (3) in FIG. 11. Note that it is effective to determine an upper limit value of the number of times of movement of each node to prevent a loop in which N13 or N23 is selected as a vertex node of a subtree in (2) in FIG. 11, N32 returns to under N22, and N32 is repeatedly moved under N22 and N23.

(41) The tree shown in (3) in FIG. 11 is taken to be an output tree. This is because even if N11 or N21 is selected as a vertex node of a subtree, the number of packets is increased by two if N31 is moved from under N21 to under N22 (returns to the state shown in (2) in FIG. 11). For the same reason, N32 is not moved even if N13 or N23 is selected as a vertex node of a subtree.

(42) <Example of Application to MECAT-RN Problem>

(43) FIG. 12 shows an example of movement of nodes when the present embodiment is applied to the MECAT-RN problem. In this example, a tree that includes relay nodes is already created using the (3,2)—LAST algorithm as shown in (1) in FIG. 12. In FIG. 12, r1 and r2 represent relay nodes and other nodes represent sensor nodes. Solid line arrows show adjacency relationships between tree nodes, and sensor reports are transferred from lower nodes to upper nodes along the solid lines, and finally transmitted to a root node 0. Dotted lines show adjacency relationships between nodes, which are not used in the tree. A numeral shown beside each link indicates the number of packets transmitted on the link, and the data aggregation rate S is five.

(44) (1) in FIG. 12 shows a case in which any of N12, r2, and N22 is selected as a vertex node of a subtree in STEP 102 in FIG. 10, but even if another node (r1, N11, or N13) is selected as a vertex node, node under the selected node is not moved. This is because the number of packets on the tree is increased in both of a case in which N21 is moved to under N31 and a case in which N23 is moved to under N32. If any of N12, r2, and N22 is selected as a vertex node, moving N31 from under N22 to under N21 or moving N32 from under N22 to under N23 is considered in STEP 104 in FIG. 10. In both cases, the number of packets does not change between before and after the movement, and therefore either of N31 and N32 is selected to be moved. In (2) in FIG. 12, it is assumed that N32 has been moved to under N23 in STEP 101 in FIG. 10.

(45) In the tree shown in (2) in FIG. 12, it is assumed that any of N12, r2, and N22 is selected again as a vertex node of a subtree in STEP 102 in FIG. 10, but if N13 or N23 is selected, N32 returns to under N22. To avoid such a loop of movement, it is effective to set an upper limit value of the number of times of movement.

(46) In (2) in FIG. 12, moving N31 from under N22 to under N21 is considered, and N31 is moved to under N21 because as a result of this movement, the number of packets is reduced by one on each of the links between N22 and r2, r2 and N12, and N12 and 0 and a total of three packets are reduced, as shown in (3) in FIG. 12.

(47) The tree shown in (3) in FIG. 12 is taken to be an output tree. This is because even if N11 or N21 is selected as a vertex node of a subtree, the number of packets is increased by three if N31 is moved from under N21 to under N22 (returns to the state shown in (2) in FIG. 12). For the same reason, N32 is not moved even if N13 or N23 is selected as a vertex node of a subtree.

(48) <Effects of Embodiment of the Invention>

(49) As described above, according to the present embodiment, even in cases such as those described with reference to FIGS. 6 to 8, the number of packets transmitted on the sensor tree can be reduced as a result of patterns of movement of nodes on the sensor tree being increased, and the energy consumption on the sensor tree can be reduced.

(50) For example, in FIG. 6, transition from (1) to (2) or (3) can be realized according to the present embodiment, although this cannot be realized using the method described in NPL 4. In a case in which the interim tree shown in (2) in FIG. 6 is created, if N22 or N12 is selected next as a vertex node of a subtree in STEP 102 in FIG. 10, N31 will be moved from under N22 to under N21, and the ideal movement shown in FIG. 7 will be realized. Also, in a case in which the interim tree shown in (3) in FIG. 6 created, if N22 or N12 is selected next as a vertex node of a subtree in STEP 102 in FIG. 10, N32 will be moved from under N22 to under N23, and the ideal movement shown in FIG. 7 will be realized. As described above, the possibility that an interim tree such as that shown in (2) or (3) in FIG. 6, which cannot be realized in the method described in NPL 4, is created in STEP 101 in FIG. 10 is increased, and therefore, the possibility that an ideal tree for minimizing the number of packets on the tree, such as that shown in FIG. 7 or 8, is created is increased.

(51) FIGS. 13 to 15 show results of simulation of an effect of reducing the number of packets and a processing load according to the present embodiment.

(52) Thousand sensor nodes were randomly arranged on a 400 m×400 m plane in a computer simulation environment, while setting the shortest distance between two different sensors to 10 m, and then adjacency relationships were created between sensor nodes located within a transmission distance of sensor signals, which was 25 m. As a result, adjacency relationships with an average of about 11.3 nodes were created per sensor node. Results obtained by creating a shortest path tree (initial tree) through breath first search and then applying the present embodiment to the initial tree in this environment are shown.

(53) Evaluation was performed under conditions where uniform random numbers from 1 to 5 were set as the numbers of sensor reports of respective sensors. FIG. 13 shows comparison between a conventional method (NPL 4) and a proposed method (the present embodiment) in terms of the number of packets reduced from the initial tree. The horizontal axis of the graph indicates the data aggregation rate (S). The maximum number of times each node was selected as a vertex node of a subtree was 10, and the maximum number of times of movement of each node was 10. That is, the only difference between the proposed method and the conventional method was in that, if nodes under a vertex node of a selected subtree included only nodes that did not have the effect of reducing the number of packets, whether or not to move those nodes up to the upper limit of the number of times of movement.

(54) FIG. 13 shows the number of packets reduced from the total number of packets in one data collection cycle with respect to shortest path trees that were respectively obtained by moving nodes using the conventional method and the proposed method. At all data aggregation rates (S), the number of reduced packets was increased by 12% to 36% by the proposed method, when compared to the conventional method.

(55) On the other hand, in the proposed method, even if the number of packets is not reduced as a result of a node being moved once, the node is moved up to the upper limit of the number of times of movement, and therefore nodes are moved many times until the flow shown in FIG. 10 ends. In order to evaluate a load of such movement, FIG. 14 shows the total number of times of movement with respect to the proposed method and the conventional method. An average number of times of movement was 68 in the conventional method for all values of S, but the proposed method required an average of 2821 times of movement. However, from comparison of the total movement time shown in FIG. 15, it can be found that an average total time that movement in the proposed method took was 6.4 seconds, and when compared to an average of 1.6 seconds in the conventional method, an average overhead was only 4.8 seconds.

(56) Usually, a tree need not be created in real time and the frequency of creation of trees is not high, and therefore the overhead of about 5 seconds will not be a big problem.

(57) <Example of Hardware Configuration>

(58) FIG. 16 shows an example of a hardware configuration of the path selection apparatus 100 in an embodiment of the present invention. The path selection apparatus 100 may also be a computer that is constituted by a processor such as a CPU (Central Processing Unit) 201, a memory device 202 such as a RAM (Random Access Memory) or ROM (Read Only Memory), a storage device 203 such as a hard disk, and the like. For example, functions and processing of the path selection apparatus 100 are realized as a result of the CPU 201 executing data or programs stored in the storage device 203 or the memory device 202. Also, information necessary for the path selection apparatus 100 may also be input from an input/output interface device 204, and results obtained by the path selection apparatus 100 may also be output from the input/output interface device 204.

(59) <Supplementary Notes>

(60) The path selection apparatus according to an embodiment of the present invention is described using a functional block diagram for the sake of convenience of description, but the path selection apparatus according to an embodiment of the present invention may also be realized by hardware, software, or a combination of hardware and software. For example, an embodiment of the present invention may also be realized by a program that causes a computer to realize functions of the path selection apparatus according to an embodiment of the present invention, a program that causes a computer to execute each step of a method according to an embodiment of the present invention, and the like. Also, functional units may also be used in combination as necessary. Also, a method according to an embodiment of the present invention may also be performed in order differing from that described in the embodiment.

(61) Although a method for reducing the energy consumption of nodes on a sensor tree has been described, the present invention is not limited to the above-described embodiment, and various changes and applications can be made within the scope of the claims.

REFERENCE SIGNS LIST

(62) 100 Path selection apparatus 110 Node information acquisition unit 120 Routing requesting unit 130 Route determination unit 131 WSN recognition unit 132 Initial tree creation unit 133 Sensor report number calculation unit 134 Node moving unit 140 WSN Storing unit 150 Tree storing unit 201 CPU 202 Memory device 203 Storage device 204 Input/output interface device