JP2017038148A - Tree route determination device and tree route determination method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently determine a tree route when creating a sensor tree composed of sensor nodes. SOLUTION: In a system having a root sensor node in a sensor tree and a floating sensor not connected to the sensor tree, a connection relationship between the floating sensor and a parent tree sensor node adjacent to the floating sensor is determined. In the tree route determination device, a sensor information acquisition means for acquiring information on the floating sensor for each level defined as the number of hops from the route sensor node, and a new tree sensor at the level for acquiring information on the floating sensor. As the node, a route determination means for connecting the floating sensor directly under the parent tree sensor node having a small level is provided. [Selection diagram] FIG. 4

Description

  The present invention relates to a technique for creating a data collection tree composed of a plurality of sensors having a root sensor node as a vertex on a wireless sensor network (WSN). In such a data collection tree, each tree sensor node on the tree repeats a collection cycle in which data is transferred along the tree to the root sensor node, thereby periodically collecting the data collected by the root sensor node to the base station. Send.

  Sensors are placed in specific locations / regions, and the humidity, temperature, gas concentration, etc. of the target location are measured by the sensors. The average value, maximum / minimum values, etc. are collected in the data collection tree, and the base from the root sensor node RPL (Routing Protocol for Low-power and Lossy) is a technology that makes it possible to analyze the target area by notifying the station, or to collect information such as gas meters and electric meters periodically in the data collection tree. Networks) protocol (Non-Patent Document 1) has been standardized.

  Many sensors are battery-operated, and a tree having a long tree life that maximizes the number of data collection tree collection cycles within the battery life of each sensor is required. Also, if the number of hops from each leaf sensor node to the root sensor node in the tree is large, the data arrival rate will be low, so a tree consisting of only the path with the shortest number of hops to the root sensor node (shortest path sensor) (Non-patent document 2), and it is required to extend the life of the shortest path sensor tree.

T. Winter, et al., "RPL: IPv6 Routing Protocol for Low-power and Lossy Networks", RFC6550, IETF, March 2012. C. Liu and G. Cao, "Distributed Monitoring and Aggregation in Wireless Sensor Networks", IEEE Infocom, 2010.

  However, in the existing tree path selection method represented by RPL of Non-Patent Document 1, each floating sensor that does not belong to the tree autonomously belongs to the tree (a tree sensor node). If it is a tree sensor node, an operation of connecting the floating sensor immediately below the tree sensor node is executed, which causes a problem that the amount of calculation increases. This problem will be described using an example shown in FIG.

  In the example shown in FIG. 1, it is assumed that the sensor constituting the tree is only the root sensor node R, and the other sensors are floating sensors that do not belong to the tree. Moreover, the dotted line in a figure shows the adjacent relationship between sensors, and the level has shown the shortest hop number from R of each sensor. Each sensor has L1-1, L1-2, L2-1, ... In this way, a code including a level and a sensor identification number within the level is attached. For example, L1-1 indicates the level 1 sensor 1. In addition, there is a case in which all sensors within a certain level are represented by expressing them with * without specifying an identification number (for example, L2- *, L3- *).

  In the example shown in FIG. 1, each sensor must check whether it has R as an adjacent sensor by checking all its adjacent sensors. As a result, since only L1-1 and L1-2 are adjacent to R, first, L1-1 and L1-2 are arranged directly under R on the tree as tree sensor nodes. Next, when determining the L2 (level 2) tree sensor node, the L2- * and L3- * floating sensors must again check all their neighboring sensors. Therefore, if the maximum level is h and the number of adjacent sensors (links) in the WSN is l (Note: L in the alphabet), the amount of calculation of O (hl) is required. This is because it is necessary to investigate a maximum of h times for a certain adjacency relationship.

  The O notation (O-notation) used in the O (hl) above is one of the methods for expressing the computational complexity of the algorithm, and indicates the asymptotic computational complexity when the problem size is increased. Is. O is called order. The O notation is effective for expressing the upper limit of the calculation amount. The definition of O (g (n)) is shown below.

  First,

とする。

And

  At this time, a set of f is defined using O as follows.

例１、例２を以下に示す。

Examples 1 and 2 are shown below.

上記の定義、及び例で示すように、f(n)∈O(g(n))とは、ある定数c、n₀が存在し、nがn₀より大きいときには必ず0≦f(n)≦c・g(n)となることを意味する。

As shown in the above definitions and examples, f (n) ∈O (g (n)) means that a constant c, n ₀ exists, and when n is larger than n _0, 0 ≦ f (n) It means that ≦ c · g (n).

  The second problem in the prior art is that the created shortest path sensor tree is not necessarily efficient in terms of energy usage and tree life. This problem will be described with reference to FIG.

  In the example of FIG. 2, the data aggregation rate q is set to q = 4. The data aggregation rate indicates the number of sensor data that can be aggregated into one packet when sensor data is collected from the leaf sensor node L3- * to the root sensor node R in the data collection tree as shown in FIG. For example, in the packet from L1-1 to R shown in FIG. 2A, four sensor data L3-1, L3-2, L2-1, and L1-1 are collected. In the example of FIG. 2, the number shown next to the link between the tree sensor nodes indicates the number of transmission packets required in one data collection cycle.

  When the shortest path sensor tree is created by the method described with reference to FIG. 1, the number of tree sensor nodes may be arranged in a balanced manner between the subtrees as shown in FIG. In some cases, the tree sensor nodes are biased between the subtrees as shown in FIG. In the case of FIG. 2B, the number of packet transmissions required in each section from L2-2 to L1-2 and L1-2 to R is 2, respectively, and the total number of packet transmissions is the case of FIG. It will be 2 larger than In the case of FIG. 2B, since the tree sensor node L2-2 is arranged immediately below, the number of packet receptions is 4, and the energy required for packet reception becomes large. There is also a problem that the energy allocated to is consumed faster than others.

  The present invention has been made in view of the above points, and an object of the present invention is to provide a technology that enables efficient tree path determination when creating a sensor tree composed of sensor nodes. .

According to an embodiment of the present invention, in a system having a root sensor node in a sensor tree and a floating sensor not connected to the sensor tree, the floating sensor and a parent tree sensor node adjacent to the floating sensor A tree path determination device for determining a connection relationship between
Sensor information acquisition means for acquiring information of the floating sensor for each level defined as the number of hops from the route sensor node;
A tree path determination device comprising: path determination means for connecting the floating sensor directly below a small parent tree sensor node of one level as a new tree sensor node at a level for acquiring information of the floating sensor Is provided.

According to an embodiment of the present invention, in a system having a root sensor node in a sensor tree and a floating sensor not connected to the sensor tree, the floating sensor and a parent tree sensor node adjacent to the floating sensor A tree path determination method executed by a tree path determination device that determines a connection relationship between
A sensor information acquisition step for acquiring floating sensor information for each level defined as the number of hops from the route sensor node;
A path determining step of connecting the floating sensor directly below a small parent tree sensor node of one level as a new tree sensor node at a level for acquiring information of the floating sensor; Is provided.

  According to the embodiment of the present invention, there is provided a technique capable of efficiently determining a tree path when creating a sensor tree including sensor nodes.

It is a figure for demonstrating a prior art. It is a figure for demonstrating a prior art. It is a figure which shows the system configuration | structure which concerns on embodiment of this invention. 2 is a configuration diagram of a route sensor node R. FIG. It is a figure for demonstrating a balance function. It is a figure which shows the example in case a balance function is not suitable. It is a figure for demonstrating the process which connects a floating sensor to a parent preferentially. It is a figure for demonstrating an effect.

  Embodiments of the present invention will be described below with reference to the drawings. The embodiment described below is only an example, and the embodiment to which the present invention is applied is not limited to the following embodiment.

(System configuration)
In the present embodiment, a data collection tree including a plurality of sensors having a root sensor node R as a vertex is created on a wireless sensor network (WSN). FIG. 3 is a diagram showing a system configuration according to the present embodiment. The state shown in FIG. 3 is the same as that in FIG. 1, and the sensor constituting the tree is only the root sensor node R, and the other sensors are floating sensors that do not belong to the tree. As already explained, the dotted line in the figure indicates the adjacent relationship between the sensors, and the level indicates the shortest hop number from R of each sensor. Each sensor has L1-1, L1-2, L2-1, ... In this way, a code including a level and a sensor identification number within the level is attached. In FIG. 3, a line with an arrow connecting the sensors is a line for explaining the operation, which will be described later.

  Each sensor is a device including a wireless communication function, a sensor data collection function, a packet transmission / reception function, and the like. Each sensor includes a function of detecting an adjacent sensor adjacent to the sensor based on the adjacent sensor acquisition request and notifying the request source of identification information of the adjacent sensor.

  In the present embodiment, sensor A recognizes sensor B as an adjacent sensor to sensor A when the received power of a signal received by one sensor A from another sensor B is greater than or equal to a predetermined threshold.

  The route sensor node R is a device (tree route determination device) that determines the tree route of the shortest route sensor tree configured by the shortest route path. The root sensor node R acquires a floating sensor for each level defined as the number of hops from the root sensor node R, and uses the floating sensor as a new tree sensor node of the level, and a small parent tree sensor node of one level. It has a function of determining a tree path by connecting directly below. When the root sensor node R acquires a floating sensor at a new level, the root sensor node R acquires an adjacent sensor of a sensor that is already a tree sensor node at a level one level lower than the level, and the adjacent sensor If the tree sensor node is not lower than the level, the adjacent sensor is connected immediately below it as a parent tree sensor node with a sensor of the next smaller level that is adjacent to the adjacent sensor. Next, a specific configuration example of the route sensor node R will be described.

  FIG. 4 is a diagram illustrating a configuration example of the route sensor node R. As shown in FIG. 4, the route sensor node R includes a routing module RM. The routing module RM includes an adjacent sensor information acquisition unit 1, a routing request unit 2, a level-by-level route determination unit 3, a tree path final determination unit 4, an adjacent sensor list storage unit 5, and a tree node storage unit 6. The level-by-level route determination unit 3 includes a common ancestor sensor node search unit 31 and a parent-to-parent movement determination unit 32. The functional outline of each functional unit is as follows.

  The adjacent sensor information acquisition unit 1 acquires an adjacent sensor adjacent to the root sensor node R itself, and transmits an adjacent sensor acquisition request to the tree sensor node that configures the tree. Get adjacent sensors adjacent to the tree sensor node. In this embodiment, “acquiring an adjacent sensor” means acquiring information (identification information or the like) indicating the adjacent sensor. For convenience, the expression “acquire adjacent sensor” is used.

  The routing request unit 2 sets the routing for each tree sensor node so that the packet is transferred according to the finally determined tree path.

  For each level, the route determination unit 3 for each level performs processing such as connecting a new tree sensor node of the level directly under a small parent tree sensor node of one level. The common ancestor sensor node search unit 31 and the parent-to-parent movement determination unit 32 included in the level-by-level route determination unit 3 execute processing related to a balance function described later. The tree path final decision unit 4 makes a routing request to the routing request unit 2 when detecting that all levels of floating sensors have been decided as tree sensor nodes.

  The adjacent sensor list storage unit 5 stores, for each node determined as a tree sensor node, a list of adjacent sensors adjacent to the node. In the present embodiment, tree sensor nodes are determined for each level in order from the smallest level. Therefore, neighboring sensors adjacent to the tree sensor node of the level are stored in the neighboring sensor list storage unit 5 in order from the smallest level. When the adjacent sensor is determined as a tree sensor node, the adjacent sensor is deleted from the adjacent sensor list storage unit 5. FIG. 4 shows a state where adjacent sensors (identification information) adjacent to the level 2 tree sensor node are stored as an example.

  The tree node storage unit 6 stores information on the determined tree (sensor node, connection relationship, etc.).

  The route sensor node R according to the present embodiment can be realized, for example, by causing a computer having a wireless communication function to execute a program describing the processing contents described in the present embodiment. That is, the function of the route sensor node R is realized by executing a program corresponding to the process executed by the route sensor node R using hardware resources such as a CPU and a memory built in the computer. Is possible. The above-mentioned program can be recorded on a computer-readable recording medium (portable memory or the like), stored, or distributed. It is also possible to provide the program through a network such as the Internet or electronic mail.

  In the present embodiment, the tree path determination device is assumed to be the root sensor node R, but this is not essential, and the function of the tree path determination device may be provided to a sensor node other than the root sensor node R. However, the tree path determination device may be provided outside the tree as a device different from the sensor node.

(Operation of route sensor node R)
Hereinafter, a tree path determination process in the root sensor node R having the above-described configuration will be described. Hereinafter, for convenience of explanation, the root sensor node R is denoted as R.

<Basic processing>
As already described, in the configuration shown in FIG. 3, only R is a tree sensor node at first. Next, the adjacent sensor information acquisition unit 1 of R acquires L1-1 and L1-2 that are R's adjacent sensors, and stores the acquisition results (L1-1 and L1-2) in the adjacent sensor list storage unit 5. Store.

  The per-level route determination unit 3 in R arranges L1-1 and L1-2 as fixed tree sensor nodes directly under R on the data collection tree, and stores them in the tree node storage unit 6.

  Since a new level 1 (L1) tree sensor node has been determined, the per-level route determination unit 3 in R instructs the adjacent sensor information acquisition unit 1 to request acquisition of adjacent sensors of L1-1 and L1-2, The adjacent sensor information acquisition unit 1 transmits an adjacent sensor acquisition request to L1-1 and L1-2.

  The adjacent sensors L1-1 and L1-2 that have received the adjacent sensor acquisition request notify R of the adjacent sensors excluding their parents (in this case, R). That is, L1-1 notifies L1-2 and L2-1, and L1-2 notifies L1-1 and L2-2. These notifications are indicated by A in FIG.

  In the present embodiment, there is no particular limitation on the signal path when the adjacent sensor acquisition request is transmitted from R to the tree sensor node, and the signal path when the adjacent sensor information is notified to R from the tree sensor node. The signal may be transmitted by any route.

  The L1-1 adjacent sensor list L1-2 and L2-1 and the L1-2 adjacent sensor list L1-1 and L2-2 are stored in the adjacent sensor list storage unit 5 and the R adjacent sensor list The lists L1-2 and L1-1 are deleted from the adjacent sensor list storage unit 5. The reason is that these sensors are already connected to the tree as level 1 (L1) tree sensor nodes, and are not necessary when determining the L2 tree sensor nodes.

  Next, the per-level route determination unit 3 connects the L1-1 and L1-2 adjacent sensors stored in the adjacent sensor list storage unit 5 as L2 tree sensor nodes. At this time, only L2-1 is present in L1-1, and only L2-2 is present in L1-2 as an adjacent sensor of L2, so L2-1 is directly under L1-1 and L2-2 is L1- The connection information is stored in the tree node storage unit 6. In the example of FIG. 4, the storage information at this time is shown in the tree node storage unit 6.

  Here, since a new level 2 (L2) tree sensor node has been determined, the per-level route determination unit 3 in R sends the adjacent sensor acquisition request transmission to L2-1 and L2-2, and the adjacent sensor information acquisition unit 1 The adjacent sensor information acquisition unit 1 transmits an adjacent sensor acquisition request to each of L2-1 and L2-2.

  In response to the request from R, L2-1 and L2-2 that have received the adjacent sensor acquisition request notify R of the respective adjacent sensors. L2-1 notifies L3-1 to L3-3 as adjacent sensors, and L2-2 notifies L3-1 to L3-4 as adjacent sensors. These notifications are indicated by B in FIG.

  The adjacent sensors acquired from each of L2-1 and L2-2 are stored in the adjacent sensor list storage unit 5. In the adjacent sensor list storage unit 5, the adjacent sensor lists of L1-1 and L1-2 stored so far are replaced with the adjacent sensor lists of L2-1 and L2-2 at this time. The reason is that all L2 sensors are already stored in the tree node storage unit 6 as tree sensor nodes. In the example of FIG. 4, stored information at this time is shown in the adjacent sensor list storage unit 5.

  The adjacent sensor list storage unit 5 passes the adjacent sensors of L2-1 and L2-2 to the level-by-level route determination unit 3 in order. Alternatively, the level-by-level route determination unit 3 may sequentially read the adjacent sensors L2-1 and L2-2 from the adjacent sensor list storage unit 5. In addition, reading the adjacent sensors of L2-1 and L2-2 from the adjacent sensor list storage unit 5 in order means reading the tree sensor node in the order of the identification numbers. The sensors (L3-1 to L3-3) are read out, and then the adjacent sensors (L3-1 to L3-4) of L2-2 are read out.

  Here, the adjacent sensors of L2-1 are L3-1 to L3-3, and since these sensors have not yet participated in the tree, the route determination unit 3 for each level does not include L3-1 to L3-3. Under the condition, the tree sensor node under L2-1 is determined and stored in the tree node storage unit 6.

  Next, when the adjacent sensors L3-1 to L3-4 of L2-2 are passed to the route determiner 3 for each level, the route determiner 3 for each level first selects L3-1 as a tree sensor node directly under L2-2. Although selected, L3-1 is already selected as a tree sensor node immediately below L2-1. In the present embodiment, a certain level of sensor node is allowed to connect to only one sensor node of one smaller level sensor node. Therefore, in this embodiment, in the present embodiment, the selection of the sensor node is appropriately corrected by the balance function.

<Balance function>
The balance function is the following function. That is, the sensor selected as the adjacent sensor of the tree sensor node (new parent tree sensor node) (in this example, L2-2) one level lower is already the tree sensor node (L3-1 in this example). If it is placed directly under another parent tree sensor node (existing parent tree sensor node) (L2-1 in this example), the existing parent tree sensor node (L2-1) and the new parent tree A common ancestor sensor node (R in this example) that is a common ancestor of the sensor node (L2-2) is searched, and the subtree to which the existing parent tree sensor node (L2-1) belongs under the common ancestor sensor node Compare the number of tree sensor nodes with the number of tree sensor nodes in the subtree to which the new parent tree sensor node (L2-2) belongs. -If the difference in the number of tree sensor nodes between the two sub-trees becomes small when moving from directly under the node to the new parent tree sensor node, move the sensor from directly under the new parent tree sensor node to directly under the new parent tree sensor node. It is to move.

  More specifically, the process related to the balance function is executed by the common ancestor sensor node search unit 31 and the parent movement determination unit 32. First, the common ancestor sensor node search unit 31 finds a common ancestor tree sensor node between the existing parent tree sensor node L2-1 and the new parent tree sensor node L2-2. In this example, the common ancestor tree sensor node is R, and the number of tree sensor nodes in the subtree under it is calculated and compared. This process is executed by the parent-to-parent movement determination unit 32 in R.

  The parent-to-parent movement determination unit 32 calculates the number of tree sensor nodes of the subtree under L1-1 as five (L1-1, L2-1, L3-1, L3-2, and L3-3), and L1 The number of tree sensor nodes in the subtree under -2 is calculated as 2 (L1-2 and L2-2), and the difference is calculated as 3. Then, the parent-to-parent movement determination unit 32 confirms that the difference in the number of nodes is decreased from 3 to 1 by moving L3-1 between subtrees, and performs the movement. Even if L3-2 and L3-3 are further moved from the moved state, the difference in the number of nodes between the subtrees remains 1, so that L3-2 and L3-3 are not moved. Since L3-4 is only adjacent to L2-2, it is placed directly under L2-2. The result of this processing (content stored in the tree node storage unit 6) is shown in FIG. As shown in FIG. 5, as a result, the number of nodes in each sub-tree is 4, and the balance is maintained.

<Routing request>
When the tree path final determination unit 4 in R recognizes that floating sensors of all levels are determined as tree sensor nodes in this way, the tree path final determination unit 4 makes a routing request to the routing request unit 2. Note that this routing request can be made each time a tree node at each level is determined. The routing request unit 2 performs routing as determined based on the tree information stored in the tree node storage unit 6. In this case, the routing means setting for each sensor node constituting the tree to transfer a packet storing sensor data along the path of the tree.

<Process to preferentially connect the floating sensor to the parent>
As described above, in the case of the adjacent relationship between the sensors shown on the left side of FIG. 5, the balance function functions appropriately. However, in the case of the adjacent relationship of the sensors as shown on the left side of FIG. 6, the balance function does not work well as described below.

  In FIG. 5 and FIG. 6, the adjacency relationship differs by one section. That is, L2-1 has L3-3 as an adjacent sensor in FIG. 5, but L2-1 does not have L3-3 as an adjacent sensor in FIG. In the case of FIG. 6, when determining the tree sensor node at level 3, first, only L3-1 and L3-2 are determined as child tree sensor nodes immediately below L2-1, and then L2-2. When determining the attribution destination of L3-1 that is an adjacent sensor, the inter-parent movement determination unit 32 has 4 nodes in the subtree under L1-1 and 2 nodes in the subtree under L1-2, and L3- Since the difference in the number of nodes can be reduced to 0 by moving 1 from L2-1 to L2-2, it is determined to perform this movement. If you move L3-2 after that, the difference in the number of nodes widens and it does not move. Since L3-3 and L3-4 are floating sensors and their parents are only L2-2, they will be connected as tree sensor nodes directly under L2-2. As a result, as shown on the right side of FIG. 6, the number of nodes in the subtree under L1-2 becomes five, which is greatly unbalanced compared to the number of nodes in subtree L1-1.

  Therefore, in order to eliminate the unbalance as described above, the route determination unit 3 for each level, when a plurality of adjacent sensors exist under the new parent tree sensor node, If there is a floating sensor, connect the floating sensor first directly under the new parent tree sensor node, and then add an adjacent sensor that already has the existing parent tree sensor node as a parent. Judgment is made whether to move directly under the new parent tree sensor node.

  In other words, when there are multiple adjacent sensors of a parent tree sensor node whose level is 1 lower, by connecting the floating sensor node whose parent is not yet determined, directly under the parent, the subtree to which the new parent tree sensor node belongs It is possible to accurately reflect the number of nodes when moving. Specifically, it is as follows.

  In determining the level 3 tree sensor node in the adjacency relationship on the left side of FIG. 7 (same as the left side of FIG. 6), the level-specific route determination unit 3 first sets L3-1 and L3-2 unconditionally. Select as a tree sensor node under L2-1. Next, the route determining unit 3 for each level selects a tree sensor node immediately below L2-2. Here, L3-3 and L3-4, which are floating sensors whose parents have not yet been determined, are connected as tree sensor nodes directly under the parent (L2-2). After this, whether the adjacent sensor (L3-1, L3-2) whose parent is the existing parent tree sensor node (L2-1) is moved directly under the new parent tree sensor node (L2-2) by the balance function described above Make a judgment.

  In FIG. 7, L3-3 and L3-4 are first connected directly under L2-2 as described above, so the number of nodes in the subtree to which the new parent tree sensor node L2-2 belongs is 4, and the existing tree sensor Since the number of nodes in the subtree to which node L2-1 belongs is also 4, the inter-parent movement determination unit 32 determines that it is not necessary to move L3-1 and L3-2 from directly below L2-1 to directly below L2-2. To do. Therefore, the node number balance among the subtrees is maintained.

  In addition, when there are a plurality of adjacent sensors of the parent tree sensor node whose level is 1 lower, the process of connecting the floating sensor node whose parent is not yet determined to the immediate parent is described in the example of the adjacent relationship in FIG. However, this processing may be applied to the adjacency relationship of FIG.

(About the effect of this embodiment)
By the basic processing executed by R, a shortest path sensor tree can be created as a data collection tree. And the amount of calculation is O (l) (Note: the letter in parentheses for O () is the letter L). This is because obtaining a floating sensor at each level is possible by obtaining adjacent sensors adjacent to a tree sensor node that is one level below that level. In the present embodiment, since the same tree sensor node needs to acquire the adjacent sensor only once, it is not necessary to acquire the adjacent sensors for different levels as in the conventional method. Therefore, the calculation amount is on the order of l which is the total number of adjacent sensors. It can be seen that this calculation amount is smaller than that of the conventional method O (hl).

  In addition, the balance function can avoid a difference in the number of tree sensor nodes to be configured between the sub-trees in the data collection tree (eg, FIG. 2 (b)). Reduction of the number of transmitted packets in the sub-tree and concentration of received packets on a small number of tree sensor nodes can be avoided, and the life of the data collection tree can be extended.

  FIG. 8 shows a comparison result of the data collection tree life when the balance function is used and when the balance function is not used. As an evaluation condition in the example shown in FIG. 8, a sensor is present at a probability of 70% at each coordinate (x, y) of 50 × 50 in a computer simulation environment, and as a result, 1758 sensors are arranged. 45698 directional links were randomly created between the sensors, and adjacent relations between the sensors were created. After that, a root sensor node was set at coordinates (26, 26) close to the center of the target plane, and a data collection tree was created according to the basic processing described above. In FIG. 8, "balanced" is a tree created using the balance function, and "random" is a child tree sensor where the existing parent tree sensor node and the new parent tree sensor node do not use the balance function. If you have one, you can select one at random and create a tree.

  This evaluation result is based on the assumption that each tree sensor node can use up to 1J of energy, and it is assumed that the life of the tree is when any one of the tree sensor nodes has used up 1J during the data collection cycle. The number of cycles is evaluated. Note that the data aggregation rate (q) varies between 1 and 17, and when it is 1, multiple sensor data cannot be stored in one packet, and a packet is created for each sensor data created by each tree node sensor. And transfer to R. FIG. 8A is a diagram comparing “balanced” and “random” with the data aggregation rate on the x-axis and the number of collection cycles on the y-axis. FIG. 8B shows a normalized value of the “balanced” collection cycle number when “random” = 1.

  As shown in FIG. 8 (a), the number of collection cycles increases as the data aggregation rate increases, but it can be understood that the number of collection cycles is larger than that of random for all the aggregation rates. Further, as shown in FIG. 8B, it can be seen that the effect of increasing the life of the data collection tree is higher as the data aggregation rate is lower in balanced. The reason is that if the data aggregation rate is low, if the number of tree sensor nodes in a certain subtree is large, the number of packets sent and received in that subtree will be larger, which will have a large effect on the number of collection cycles. Conceivable.

  In addition, by using the process of preferentially connecting the floating sensor to the parent, first the floating sensor that has been established at this point as a child of the new parent tree sensor node is first connected directly below the new parent tree sensor node. After the number of tree sensor nodes located immediately below the new parent tree sensor node is updated, it is possible to determine whether or not to move a sensor having an existing parent tree sensor node as a parent to the new parent tree sensor node. .

  The present invention is not limited to the above-described embodiments, and various modifications and applications are possible within the scope of the claims.

DESCRIPTION OF SYMBOLS 1 Neighboring sensor information acquisition part 2 Routing request | requirement part 3 Route | route determination part 4 for every level Tree path final decision part 5 Adjacent sensor list storage part 6 Tree node storage part 3 Route determination part 31 for every level Common ancestor sensor node search part 32 Parent movement Judgment part

Claims (8)

Tree path determination that determines the connection relationship between the floating sensor and the parent tree sensor node adjacent to the floating sensor in a system having a root sensor node in the sensor tree and a floating sensor that is not connected to the sensor tree A device,
Sensor information acquisition means for acquiring information of the floating sensor for each level defined as the number of hops from the route sensor node;
A tree path determination device comprising: path determination means for connecting the floating sensor directly below a small parent tree sensor node of one level as a new tree sensor node at a level for acquiring information of the floating sensor . The sensor information acquisition means acquires information on adjacent sensors adjacent to a sensor that is already a tree sensor node at a level one smaller than the level when acquiring information on a new level floating sensor,
If the adjacent sensor is not a tree sensor node, the route determining means connects the adjacent sensor directly below it as a parent tree sensor node with a sensor of the next lower level that is adjacent to the adjacent sensor as a parent tree sensor node. The tree path determination device according to claim 1. The sensor selected as the adjacent sensor of the new parent tree sensor node that is one level lower tree sensor node is already a tree sensor node, and is placed directly under the existing parent tree sensor node that is another parent tree sensor node. In the case where
The path determination means searches for a common ancestor sensor node that is a common ancestor of the existing parent tree sensor node and the new parent tree sensor node, and the existing parent tree sensor node belongs under the common ancestor sensor node. Compare the number of tree sensor nodes in the sub-tree to the number of tree sensor nodes in the sub-tree to which the new parent tree sensor node belongs, and temporarily move the sensor from directly under the existing parent tree sensor node to directly under the new parent tree sensor node. If the difference in the number of tree sensor nodes between the two subtrees is small, the sensor is moved from directly below the existing parent tree sensor node to directly below the new parent tree sensor node. The tree path determination device according to claim 2. In the case where there are a plurality of adjacent sensors under the new parent tree sensor node,
The path determining means determines whether or not a floating sensor exists among the plurality of adjacent sensors, and when the floating sensor exists, first connects the floating sensor directly below the new parent tree sensor node. The tree path determination device according to claim 3, wherein thereafter, it is determined whether or not to move an adjacent sensor having the existing parent tree sensor node as a parent immediately below the new parent tree sensor node. Tree path determination that determines the connection relationship between the floating sensor and the parent tree sensor node adjacent to the floating sensor in a system having a root sensor node in the sensor tree and a floating sensor that is not connected to the sensor tree A tree path determination method executed by a device,
A sensor information acquisition step for acquiring floating sensor information for each level defined as the number of hops from the route sensor node;
A path determining step of connecting the floating sensor directly below a small parent tree sensor node of one level as a new tree sensor node at a level for acquiring information of the floating sensor; . In the sensor information acquisition step, when acquiring information on a new level of floating sensor, the tree path determination device is adjacent to a sensor that is already a tree sensor node at a level one lower than the level. Get sensor information,
In the route determination step, when the adjacent sensor is not a tree sensor node, the tree route determination device sets the adjacent sensor as a parent tree sensor node as a parent tree sensor node immediately below the adjacent sensor. The tree path determination method according to claim 5, wherein: The sensor selected as the adjacent sensor of the new parent tree sensor node that is one level lower tree sensor node is already a tree sensor node, and is placed directly under the existing parent tree sensor node that is another parent tree sensor node. In the case where
In the path determining step, the tree path determining apparatus searches for a common ancestor sensor node that is a common ancestor of the existing parent tree sensor node and the new parent tree sensor node, and the subordinate subordinate to the common ancestor sensor node The number of tree sensor nodes in the subtree to which the existing parent tree sensor node belongs is compared with the number of tree sensor nodes in the subtree to which the new parent tree sensor node belongs. If the difference between the number of tree sensor nodes between the two sub-trees becomes small when the node is moved directly under the parent tree sensor node, the sensor is moved from directly under the existing parent tree sensor node to directly under the new parent tree sensor node. It is made to move. Tree path determination method described in 1. In the case where there are a plurality of adjacent sensors under the new parent tree sensor node,
In the path determination step, the tree path determination device determines whether or not a floating sensor exists among the plurality of adjacent sensors, and when the floating sensor exists, the floating path sensor is used as the new parent tree sensor. 8. The method according to claim 7, wherein it is determined whether or not an adjacent sensor having the existing parent tree sensor node as a parent is moved immediately below the new parent tree sensor node after first connecting directly under the node. Tree path determination method.

Images