WO2010055602A1 - Network system - Google Patents

Abstract

A network system constructs network topology such that the occurrence of voids is minimized by the autonomous distributed operation of multiple nodes each provided with a communication means and a movement means.  The network system comprises multiple nodes (100) each provided with a communication means (110) and a movement means (120).  Each of the nodes (100) searches for a nearby different node (100) communicable via the communication means (110) while moving by means of the movement means (120), and couples with the searched different node (100) with a space that satisfies a predetermined condition maintained therebetween, and thus a cluster composed of two or more nodes (100) is generated.  Each of the nodes (100) composing the cluster further searches for another nearby different node (100) communicable via the communication means (110) while moving by means of the movement means (120) with the coupled state of the coupled nodes (100) maintained, and couples with the searched different node (100) with the space that satisfies the predetermined condition maintained therebetween.

Description

Network system

The present invention relates to a network system that constructs a network topology by autonomously distributed operation of a plurality of nodes having a communication function and a movement function.

There are a wireless network system and a sensor network system for constructing an ad-hoc network by wireless communication as network systems for which demand is expected to increase sufficiently in the future.

In constructing an ad-hoc network by wireless communication, each wireless node basically forms a network topology in an autonomous and distributed manner, and exchanges information therein.

The sensor network is composed of a plurality of sensor nodes equipped with sensors, and is used to collect real-world information such as temperature simultaneously over a wide area. In the past, sensor networks may be expensive, and there is a special node called a sink node that has functions for collecting information from sensor nodes and distributing information to sensor nodes. Information was collected directly from the sensor nodes and the control information was distributed to them. Recently, however, it has become possible to reduce the cost and increase the functionality of sensor nodes, so that the sensor node itself has a communication function and exchanges information with the sink node via other adjacent sensor nodes. The form of performing is attracting attention. Such a sensor network can be regarded as a network in which a wireless node in the wireless network described above has a sensor function.

In a sensor network composed of a large number of sensor nodes having sensors and wireless communication functions, each sensor node collects and distributes information by communicating with other adjacent sensor nodes. Accordingly, the topology of the sensor network is such that at least one other sensor node exists in a communicable area determined by a circle whose radius is a communicable distance determined by the performance of the wireless communication function centered on each sensor node. Must be determined. However, if the area that can be sensed by the sensor of the sensor node is smaller than the communicable area and the target area is sensed at high density, the distance between adjacent sensor nodes must be shorter than the communicable distance. There is.

The method of configuring a network topology that satisfies the above conditions is based on the premise that each sensor node can move autonomously and a static topology configuration method that assumes that each sensor node does not move. And a dynamic topology configuration method.

A typical example of a static topology configuration method is a method of distributing sensor nodes at high density or a method of manually installing sensor nodes. However, since it is difficult to distribute a large number of sensor nodes at a uniform density, density density is likely to occur. Sensor nodes are wasted at high density locations. Moreover, the method of installing by hand is difficult to apply when sensing a place where a person cannot easily step on, such as a mountain or a forest, in addition to requiring a lot of manpower.

On the other hand, the dynamic topology configuration method has many advantages over the static topology configuration method, such as the ability to configure the network topology by autonomously distributed operation of each node without human intervention. Have. The present invention relates to such a dynamic topology configuration method.

An example of a dynamic topology configuration method is described in Patent Document 1. In the sensor network described in Patent Document 1, each sensor node has an Expand state and a Bridge state that search for neighboring nodes while moving using a moving function, and a Stay state in which the movement is stopped. Two or more nodes that are independent of each other not having a neighboring node and not having a neighboring node relationship with each other in the Bridge state when transitioning to the Stay state occurs when connection to neighboring nodes in one State state becomes possible When the connection becomes possible (the state does not matter), the state transitions to the Stay state together with these two or more nodes, and each node dynamically switches between the Expand state and the Bridge state while staying A network topology is formed by transitioning to a state.

Further, in order to prevent the range (coverage) covered by all the sensor nodes from becoming small due to the transition to the Stay state when the two nodes are too close together, In order to prevent the occurrence of communication interruption due to the transition to the Stay state at the limit of the mutual radio wave arrival distance, the neighboring node whose radio wave intensity exceeds a predetermined value and the neighboring node whose radio wave intensity falls below a predetermined value And try to avoid connection relationships.

JP 2006-165695 A

According to the sensor network described in Patent Document 1, it is possible to construct a network topology in an autonomous and distributed manner even if each sensor node does not have an advanced positioning function such as GPS. However, there is a problem that a void that is not covered by any node is easily formed inside a closed curve that surrounds all the nodes. The reason is that when the nodes in the Expand state become connectable to a neighboring node in one Stay state, the node transitions to the Stay state and stops moving, and the nodes in the Bridge state are not related to each other in the neighboring nodes. If it is possible to connect to two or more nodes that are independent and do not have the same neighboring node, the transition to the state state is made together with these two or more nodes. This is because once the nodes are connected, the positions of the plurality of nodes are fixed.

An object of the present invention is to provide a gap that is not covered by any node inside a closed curve surrounding all nodes in a network system that constructs a network topology by autonomously distributed operation of a plurality of nodes having communication functions and mobile functions. It is to construct a network topology so as to prevent as much as possible.

The network system of the present invention
A network system comprising a plurality of nodes provided with communication means and movement means,
Each node searches for other neighboring nodes capable of communicating by the communication means while moving using the moving means, and joins with the searched other nodes while maintaining a predetermined condition. Creates a cluster consisting of two or more nodes,
Each node constituting the cluster searches for another node in the vicinity that can communicate with the communication unit while moving using the moving unit while maintaining the combined state of the connected nodes. It joins with this searched other node while maintaining an interval that satisfies the predetermined condition.
The structure is taken.

The network system construction method of the present invention includes:
A method of constructing a network system composed of a plurality of nodes provided with communication means and movement means,
Each node searches for other neighboring nodes capable of communicating by the communication means while moving using the moving means, and joins with the searched other nodes while maintaining a predetermined condition. Creates a cluster consisting of two or more nodes,
Each node constituting the cluster searches for another node in the vicinity that can communicate with the communication unit while moving using the moving unit while maintaining the combined state of the connected nodes. It joins with this searched other node while maintaining an interval that satisfies the predetermined condition.
The structure is taken.

The node device of the present invention
A node device comprising communication means, movement means and control means,
Under the control of the control means, a search is made for other nearby nodes capable of communication by the communication means while moving using the moving means, and an interval satisfying a predetermined condition is maintained with the other searched nodes. By combining, create a cluster consisting of two or more nodes,
Further, while searching for another node in the neighborhood that can communicate with the communication means while moving using the moving means while maintaining the connected state of the connected nodes, the other nodes searched Are combined with an interval satisfying the above predetermined condition,
The structure is taken.

The program of the present invention
A computer constituting a node device including a communication unit and a movement unit,
2 or more by searching for other neighboring nodes capable of communicating by the communication means while moving by using the moving means, and combining the searched other nodes with an interval satisfying a predetermined condition. Further, another node in the neighborhood that can communicate with the communication unit while moving using the moving unit while maintaining the coupled state of the coupled nodes is generated. A control means for performing control to search for and combine with other searched nodes while maintaining an interval satisfying the predetermined condition,
It is a program that functions as

According to the present invention, it is possible to construct a network topology in which a void that is not covered by any node is generated as much as possible inside a closed curve that surrounds all the nodes by autonomously distributed operation of a plurality of nodes.

It is a block diagram which shows the structural example of the sensor node which concerns on the 1st Embodiment of this invention. It is a flowchart which shows the process example of the control part of the sensor node which concerns on the 1st Embodiment of this invention. It is a figure for demonstrating the movement of the sensor node couple | bonded with two other nodes in the 1st Embodiment of this invention. It is a figure which shows an example of the formula which describes the moving speed and direction of a movement of the sensor node couple | bonded with two other nodes in the 1st Embodiment of this invention. In the 1st Embodiment of this invention, it is a figure which shows an example of the formula which describes the moving speed and the direction of a movement of a two-dimensional random walk. In the 1st Embodiment of this invention, it is a schematic diagram of the initial state suitably scattered in the area which many sensor nodes want to sense. In the 1st Embodiment of this invention, it is a schematic diagram which shows a state when two sensor nodes which were carrying out the two-dimensional random walk have mutually approached and couple | bonded. In the 1st Embodiment of this invention, it is a schematic diagram which shows a state when the cluster comprised from two sensor nodes and one sensor node each approached and couple | bonded together, carrying out two-dimensional random walk. It is a schematic diagram which shows the mode of the movement of the cluster comprised from three sensor nodes in the 1st Embodiment of this invention. FIG. 3 is a schematic diagram illustrating a state in which three sensor nodes are coupled to each other to form a regular triangular cluster in the first embodiment of the present invention. It is a schematic diagram which shows a mode that the cluster with a space | gap changes to the cluster without a space | gap in the 1st Embodiment of this invention. In the 1st Embodiment of this invention, it is a schematic diagram which shows a part of largest cluster formed by combining all the sensor nodes. In the first embodiment of the present invention, a moving method for quickly transitioning a cluster in which three sensor nodes are connected in a row to a cluster in which three sensor nodes are connected to each other to form a regular triangle It is a schematic diagram which shows. It is a block diagram of the network system which concerns on the 2nd Embodiment of this invention.

Next, embodiments of the present invention will be described in detail with reference to the drawings.

Referring to FIG. 1, a sensor node 10 constituting a network system according to the present invention includes a sensor function unit 11, a wireless communication function unit 12, a movement function unit 13, a storage unit 14, and a control unit 15. ing.

The sensor function unit 11 includes sensors for collecting real-world environmental information such as a temperature sensor and a pressure sensor.

The wireless communication function unit 12 has a function of performing wireless communication with other sensor nodes according to IEEE802.11, Bluetooth (registered trademark), and other arbitrary communication protocols. In the case of the present embodiment, the wireless communication function unit 12 has a direction detection function that detects from which direction the communication partner has seen wireless communication as viewed from its own node. The direction of the other node viewed from the own node can be measured, for example, by rotating the antenna with strong directivity and the antenna rotation angle when receiving the radio wave from the target other node at the highest level. Of course, it is also possible to measure the existence direction of other nodes by any other method such as electronically switching the direction of directivity.

The movement function unit 13 is configured by a mechanism such as a wheel, a belt conveyor, or a movable leg, and has a function of moving the node 10 at a movement direction and a movement speed instructed from the control unit 15.

The storage unit 14 is configured by a semiconductor memory, a magnetic disk, or the like, and stores a density value, a binding list, etc., which will be described later, and a program for controlling the operation of the sensor node 10.

The control unit 15 is configured by a CPU or the like, and reads a program stored in the storage unit 14 and executes the program, thereby performing a sensing operation by the sensor function unit 11, a wireless communication operation by the wireless communication function unit 12, and a moving function. It controls the entire node including the movement operation by the unit 13.

FIG. 2 is a flowchart showing an example of a control operation by the control unit 15. Hereinafter, the operation of the sensor node 10 according to the present embodiment will be described with reference to FIG.

The control unit 15 of the sensor node 10 performs an initial setting process when activated by power-on or the like (step S101). In this initial setting process, the density value of the own node stored in the storage unit 14 is set to an initial value of 1. The density value is a variable that is increased or decreased according to the number of other nodes coupled to the own node. In this embodiment, the value is incremented by 1 when not coupled to any other node, and then incremented by 1 each time coupled to one other node. On the other hand, when the connection is released due to a failure of another node or the like, the concentration value decreases conversely. In the initial setting process, the combined list stored in the storage unit 14 is set to NULL. The combined list is a list of identifiers of other nodes that are combined with the own node.

Next, the control unit 15 determines whether the density value of the node 10 is 1, 2, or 3 or more (steps S102 and S103), and performs control according to the determined density value.

(1) When the density value is 1 When the density value is 1 (YES in step S102), that is, when the own node 10 is not coupled to any other node, the control unit 15 until the other node is found. Control for searching for another node by a two-dimensional random walk is performed (steps S105 and S106).

Specifically, the control unit 15 determines a random moving direction and moving speed by, for example, a random number, and instructs the moving function unit 13 to determine the moving direction and moving speed, so that the node 10 is two-dimensional. Random walk. In addition, a search message including the current concentration value of the own node 10 and the identifier of the own node is transmitted to the surroundings by broadcast communication through the wireless communication function unit 12 at a fixed period, while receiving a search message from another node. Monitor.

Here, the communicable distance by the wireless communication function unit 12 of each sensor node 10 is fixed to a constant value Lr. Accordingly, each sensor node 10 can communicate only with other nodes existing in a circle having a radius Lr centered on the own node. The search for another node is an operation for checking whether or not there is another node that is not connected to the own node in this circle by transmitting and receiving a search message to each other.

The control unit 15 receives the search message from another node whose identifier is not described in the link list of the own node (YES in step S106), that is, the own node and the node not within the circle of radius Lr centered on the own node. When a connected other node is found, it is determined whether the number of found other nodes is singular or plural (step S112). If the number is one, a search response message including an identifier of the own node for the found other node. Is transmitted to bring the own node 10 and other nodes into a coupled state, and at the same time, the density value of the own node is incremented by one (step S114). To make the own node and the other node into a combined state, the node identifier of the other node is added to the combined list stored in the storage unit 14, and the interval between the other node and the own node described in the combined list is predetermined. Is to maintain the condition of In this way, two or more nodes maintained so that the distance between the nodes satisfies a predetermined condition constitutes one cluster. Here, as the predetermined condition, for example, the following condition a or b can be considered.

(A) The sensing areas of the two nodes are almost in contact with each other, or partially overlap with each other within a preset width.
(B) The distance between the centers of the two nodes is within a range of L _{1 which is} less than or equal to the communicable distance Lr and a distance L ₂ which is shorter than L ₁ by Δ. Here, L ₁ is desirably a distance that can suppress the deterioration of the signal-to-noise ratio between the nodes to a predetermined value or less. Further, Δ corresponds to the size of the width where the communicable areas overlap, and is set in advance. This width Δ is preferably as narrow as possible in order to maximize the range covered by all nodes.

The distance between the centers of the two nodes can be derived from the relationship between the received radio wave intensity and the distance when using radio waves for wireless communication. In addition, if the sensing area of the sensor node 10 is constant, whether the sensing areas of the two nodes are almost in contact with each other or whether they partially overlap within a preset width is derived from the relationship between the received radio wave intensity and the distance. It can be obtained from the distance between the nodes and the size of the sensing area.

If the number of discovered other nodes is plural, the control unit 15 selects another node having a larger density value in order to combine with the larger cluster side (step S113). Then, a search response message including the identifier of the own node is transmitted to bring the own node 10 and the other node into a coupled state, and the density value of the own node is incremented by 1 to 2 (step S114).

(2) When the density value is 2 When the density value is 2 (YES in step S103), that is, when the own node 10 is coupled to only one other node, the control unit 15 is not coupled to the own node. Until another other node is found, control is performed to search for another node by the two-dimensional random walk while maintaining the connection state with the already connected other node (steps S107 and S108).

Specifically, the control unit 15 determines a random moving direction and moving speed and commands the moving function unit 13 within a range in which the interval with another node that has already been combined satisfies the predetermined condition. By doing so, the self-node 10 is walked two-dimensionally while being coupled with other nodes. Similarly to the case of the density value 1, the search message is periodically transmitted, and the reception of the search message from another node is monitored. When the control unit 15 receives a search message from another node not listed in the combined list (YES in step S108), one of the other nodes found and the own node are processed by the same process as in the case of the density value 1. 10 are connected (steps S112 to S114).

(3) When the density value is 3 or more When the density value is 3 or more (NO in step S103), the control unit 15 further determines whether the density value is 3 or 4 or more (step S104).

When the density value is 3, that is, when the own node 10 is coupled to two other nodes, the control unit 15 continues to connect the two other nodes that are currently coupled until it finds another node that is not coupled to the own node. The curvature of the arc formed by the two other nodes that are currently coupled and the own node is the minimum (that is, the radius of the arc is the maximum. However, the curvature = 0 so that it is not aligned on a straight line) Control is performed to search for other nodes while moving in the moving direction (steps S110 and S111).

When the density value is 4 or more, that is, when the own node 10 is coupled to another node of 3 or more, the control unit 15 selects two other nodes having the smallest sum of density values among the coupled other nodes. (If there are a plurality of minimum pairs, an arbitrary one of them) is selected (step S109), and the process proceeds to step S110 to perform the same control as described above. That is, the control unit 15 maintains the connection state with the selected two other nodes until it finds another other node that is not connected to the own node, and Control is performed to search for other nodes while moving so that the curvature of the formed arc is minimum (that is, the radius of the arc is maximum) (steps S110 and S111).

When the control unit 15 receives a search message from another node that is not listed in the combined list (YES in step S111), the control unit 15 performs processing similar to the case of the density value 1 and one of the found other nodes and its own node. 10 are connected (steps S112 to S114).

Next, specific examples of movement control in steps S105, S107, and S110 will be described.

FIG. 3 is a diagram for explaining movement of a sensor node in which two or more other nodes are coupled to the own sensor node, and FIG. 4 is a movement speed of the sensor node in which two or more other nodes are coupled to the own sensor node. And an example of an expression describing the direction of movement. Equation 1 shown in FIG. 4 is a description in a music coordinate format, but can also be described in a two-dimensional orthogonal coordinate system. Note that these music coordinates and two-dimensional orthogonal coordinates are coordinates temporarily set by each sensor node in calculating the movement direction.

In Equation 1, k (θ, t, φ, d) is the curvature of the arc formed by the sensor node j, k joined by the sensor node i at the angle θ at time t. Here, φ is variable in the range of 0 ≦ φ ≦ 2π with the phase of the sensor node i, and this value is set to be different from other sensor nodes connected in the cluster, for example, by a random number, A cluster composed of three or more sensor nodes can move in any direction.

The first term on the right side of Equation 1 is a term for the node i to move in the radial direction of the curvature of the arc formed with the coupled node j and node k. In order to obtain the curvature of the arc formed by the own node i and the other nodes j and k, it is understood from the own node i how far the other nodes j and k exist in which direction. Need to be. The distance to the other node is known because the other node and its own node maintain a coupled state. The direction of the other node viewed from the own node is measured using the direction detection function of the wireless communication function unit 12.

The second term on the right side of Equation 1 is a term that moves to minimize the curvature over time.

The third term and the fourth term on the right side of Equation 1 are terms representing the strength of coupling, which means that the nodes with higher density d are more easily coupled. G is a positive proportionality coefficient, and its value is set so as to keep the coupling distance between the nodes within a certain range by balancing with the repulsive force according to the fifth and sixth terms.

F (r, θ, t, φ, d) of the fifth term and the sixth term of Equation 1 is a phase φ in which a sensor node i at a distance r and an angle θ from the node center is coupled at time t. This is a suppression term for achieving a distance that satisfies a predetermined condition with another sensor node of density d. For example, if the predetermined condition is that the sensing areas overlap at a certain distance, the fifth and sixth terms correspond to the repulsive force that pushes the distance between any two or more coupled sensor nodes to the limit of the sensing area. .

Next, an example of formulation of a two-dimensional random walk is shown in Equation 2 in FIG. Note that variables in () as in Equation 1 are omitted. The first term on the right side is the term of the two-dimensional random walk of the node, the second term and the third term on the right side are the terms of the attractive force from the node where the communication areas overlap (the higher the density d, the easier the coupling) The term after the term is a repulsive force that pulls the distance between nodes to the limit of the sensing area. Here, the proportionality coefficient a is a positive number. In a single node that is not coupled to any other node, the third and subsequent terms are omitted.

Next, a characteristic operation until a large number of nodes perform a two-dimensional random walk and finally one cluster is formed will be described with a specific example.

FIG. 6 is a schematic diagram of an initial state in which a large number of sensor nodes 10 are appropriately dispersed in an area to be sensed. Each sensor node 10 searches for another sensor node 10 that can communicate while performing a two-dimensional random walk. It is in a state of being. In the figure, the center black circle indicates the sensor node 10, and the circle centered on the black circle indicates a communicable area. In an initial state in which each sensor node 10 is not coupled to any other sensor node, the density value of each sensor node is 1.

FIG. 7 schematically shows a state in which two sensor nodes A and B that have been performing a two-dimensional random walk are coupled close to each other. In the figure, an outer circle in each sensor node indicates a communicable area, an inner filled circle indicates a sensing area, and a small white circle at the center indicates a position of the sensor node. As shown in FIG. 7, each density value changes from 1 to 2 by the combination. Further, the sensor node A and the sensor node B coupled to each other constitute one cluster, and the cluster as a whole performs a two-dimensional random walk.

FIG. 8 schematically shows a state in which the cluster composed of the sensor node A and the sensor node B and the sensor node C approach each other while two-dimensional random walking, and the sensor node C is combined with the sensor node B. Show. Due to the coupling, the density value of the sensor node C changes from 1 to 2, and the sensor node B changes from 2 to 3.

FIG. 9 is a schematic diagram showing the movement of a cluster composed of three sensor nodes A, B, and C formed as shown in FIG. The middle sensor node B moves in a direction that minimizes the curvature of the arc indicated by the broken line in the figure formed by the own node B and the other nodes A and C. On the other hand, the sensor node A that is coupled only to the sensor node B and the sensor node C that is coupled only to the sensor node B perform a two-dimensional random walk within a range in which the coupling is maintained. As a result, as a whole cluster, a two-dimensional random walk is performed while changing the positional relationship between the nodes (that is, changing the shape of the cluster). With this two-dimensional random walk, when each sensor node finds another uncoupled sensor node, it joins with it.

Here, since the sensor node A and the sensor node C are not connected to each other, the communicable areas of the sensor node A and the sensor node C overlap in the process of two-dimensional random walk while changing the positional relationship between the nodes. , Sensor node A and sensor node C are coupled, and as shown in FIG. 10, three sensor nodes A, B, and C are coupled to each other to form a regular triangular cluster.

In the initial state of FIG. 6 in which a large number of sensor nodes 10 are appropriately dispersed in the sensing target area, coupling between the sensor nodes is performed at various places as described above, and the sensor nodes 10 are configured by two or three sensor nodes. Many small clusters are formed, and these small clusters continue to move while changing shape, so that the connection with the remaining single sensor node and the connection between the small clusters are repeated. As a result, a larger-scale cluster is formed, and finally one cluster is formed.

At this time, a sensor node that is coupled to one or more other sensor nodes searches for other neighboring nodes while moving using the moving function while maintaining the coupled state of the coupled nodes. Even if a gap that is not covered by any sensor node is temporarily generated in the cluster because it is combined with other nodes that have been searched, the sensor node that has advanced in the direction of filling the gap will be connected to the cluster without the gap. And change. In particular, in the present embodiment, the sensor node coupled to two or more other sensor nodes selects a set of two other nodes having the smallest sum of density values, and the selected two other nodes and the own node. Therefore, even if a gap that is not covered by any sensor node is temporarily generated in the cluster, the sensor nodes around the gap are moved in the direction of the gap. It moves and quickly forms clusters without voids. FIG. 11 schematically shows such a state.

11 there are seven sensor nodes A, B, D, E, G, H, and I in contact with the air gaps existing in the cluster of FIG. In general, a sensor node in contact with a gap has a smaller density value than a sensor node whose periphery is filled with another sensor node. For this reason, the sensor nodes A, B, D, E, G, H, and I that are in contact with the air gap select a set of two nodes including the sensor nodes that are also in contact with the air gap, and the other two selected The probability of moving in the direction indicated by the arrow in the figure that minimizes the curvature of the arc formed by the node and the self node increases. Since the movement direction is toward the center of the air gap, the distance between the sensor nodes moving in the direction of the air gap gradually approaches each other, and finally the sensor nodes are coupled to each other as shown on the right side of FIG. Changes to a cluster with no voids.

The diagram on the left side of FIG. 12 is a schematic diagram showing a part of the largest cluster formed by combining all sensor nodes. Since the density value of all the sensor nodes is 4 or more, each sensor node selects a set of two other nodes having the smallest sum of density values among the other nodes connected, and this selected 2 It moves in a direction that minimizes the curvature of the arc formed by the two other nodes and its own node. In each sensor node in the cluster in which there are a plurality of pairs having the minimum sum of density values, as a result of randomly selecting a pair, the movement direction of each sensor node in the cluster becomes random. On the other hand, the sensor nodes on the outer periphery of the cluster have the smallest sum of density values in the set of adjacent sensor nodes on the outer periphery so that the curvature of the arc formed with the sensor node on the adjacent outer periphery is minimized. Moving. As a result, the shape of the cluster gradually approaches a circle, and the shape of the circle is maintained. In this way, a circular cluster having the maximum area (coverage) covered by all sensor nodes is finally generated.

Next, a description will be given of an operation in which a gap generated by a sensor node whose function is stopped is filled with a normal sensor node in the vicinity when one of the sensor nodes constituting the cluster stops its function due to a failure or the like.

As described above, the control unit 15 of each sensor node that constitutes the cluster simultaneously broadcasts a search message including the identifier of the own node by the wireless communication function unit 12 at a fixed period, and simultaneously transmits search messages from other nodes. The reception is monitored. When the node identifier included in the received search message is not described in the combined list of the own node, the control unit 15 performs the combining process with the other node as described above, but is already described in the combined list. In the case of a failure, the timer corresponding to the described node identifier is reset to the initial value. This timer counts up as time elapses, and times up when it reaches a preset value. Therefore, if another node coupled to the own node is functioning normally, the timer will not time out by receiving periodic search messages from the other node. When the function is stopped, reception of the search message from another node is interrupted, so the timer times out. The control unit 15 determines that the other node that has timed up has stopped functioning due to failure or failure, deletes the identifier of the other node from the combined list, and decreases the density value of the own node by one.

As a result, the density value of the normal sensor node that is in contact with the gap caused by the sensor node that has stopped functioning is smaller than the density value of the normal sensor node that is filled with the normal sensor node. For example, in the cluster shown on the left side of FIG. 12, when two sensor nodes indicated by bold lines stop functioning, a gap as shown on the right side of FIG. 12 is formed in the cluster. This situation is exactly the same as the situation described with reference to the diagram on the left side of FIG. Therefore, the gap generated by the sensor node whose function is stopped is filled with the normal sensor node in the vicinity by the same operation as that described with reference to FIG.

As described above, according to the present embodiment, a network topology in which a gap that is not covered by any node does not occur as much as possible inside a closed curve that surrounds all nodes is achieved by autonomously distributed operation of a plurality of nodes. Can be built. The reason for this is that each node operating as a member of the cluster maintains another coupled state of the coupled nodes, while other nodes in the neighborhood that can communicate using the communication function while moving using the move function are selected. This is because the probability that a void is generated is reduced because the search is performed and combined with other searched nodes. In particular, a sensor node combined with two or more other sensor nodes selects a set of two other nodes having the smallest sum of density values, and is formed by the selected two other nodes and the own node. According to the configuration that moves in the direction that minimizes the curvature of the arc, even if a gap that is not covered by any sensor node is temporarily generated in the cluster, the sensor nodes around the gap move in the gap direction. Finally, it is possible to form a cluster without voids in a shorter time.

Further, according to the present embodiment, when one of the sensor nodes constituting the cluster stops its function due to a failure or the like, the gap generated by the sensor node whose function has been stopped is replaced with the normal sensor node in the vicinity. It can be filled by autonomous distributed operation. The reason is that a normal sensor node that has been combined with a sensor node that has stopped functioning needs to maintain a predetermined interval with the sensor node that has stopped functioning in order to cancel the connection relationship with the sensor node that has stopped functioning. This is because the movement in the direction of the sensor node that has disappeared and has stopped functioning becomes possible, and induces an operation of being coupled with another normal sensor node in contact with the gap. In particular, a sensor node combined with two or more other sensor nodes selects a set of two other nodes having the smallest sum of density values, and is formed by the selected two other nodes and the own node. According to the configuration of moving in the direction that minimizes the curvature of the arc, the sensor nodes around the gap generated by the sensor node whose function has been stopped due to a failure or the like move in the direction of the gap. It becomes possible to solve with.

Further, a sensor node coupled to two or more other sensor nodes selects a set of two other nodes having a minimum sum of density values, and is formed by the selected two other nodes and the own node. According to the configuration of moving in the direction that minimizes the curvature of the arc, it is possible to generate a single cluster having a maximum area (coverage) covered by all sensor nodes.

It should be noted that the following various modifications can be made to the present embodiment.

In the present embodiment, the present invention is applied to a sensor network, but it can also be applied to a wireless network.

In the present embodiment, when the number of other nodes coupled to the own node is two or more, each sensor node includes two of the two or more other nodes coupled to each other that have the smallest sum of density values. The movement control is performed so that the moving direction is the direction in which the curvature of the arc formed by the other node and the own node is minimized. However, based on such movement control, different movement control may be performed under a specific situation.

For example, in order to quickly transition from the state shown in FIG. 9 where three sensor nodes are coupled in a row to the state shown in FIG. 10 where three sensor nodes are coupled to each other, as shown in FIG. A sensor node B coupled to two or more other sensor nodes A and C has a sensor node A and a sensor node C when there is a node whose density value is not 3 or more among the sensor nodes A and C. In order to make it easier to approach the node B, the moving direction of the node B may be reversed 180 degrees so that the curvature is maximized (that is, the radius of the arc is minimized).

In addition, each sensor node in which the number of other nodes coupled to the own node is two or more is determined by the failure of the other nodes in the cluster to which the node belongs, and the two other nodes having the smallest sum of density values and the own node. If it is not possible to move in the direction that minimizes the curvature of the arc formed in step 1, the direction is reversed by 180 degrees and the curvature is moved to the maximum (that is, the radius of the arc is minimum). Also good. According to such an operation, for example, it is possible to reliably prevent the nodes from continuing on the line to form a circumferential cluster. In addition, when it cannot move so that a curvature may become the maximum (that is, the radius of an arc is the minimum), it reverses direction 180 degrees again and moves to the direction which makes the curvature of an arc the minimum. Therefore, when the robot cannot move in either direction, the operation of reversing the direction by 180 degrees is repeated.

In the present embodiment, the network is configured with only sensor nodes, but nodes other than sensor nodes may be added. For example, a single node or a plurality of nodes called “sink nodes” having a function of collecting and aggregating information from sensor nodes (but sufficiently smaller than the number of sensor nodes) may be added. The sink node has a fixed density value larger than the maximum density value of the sensor node, and transmits a search message including its own node identifier and density value at a fixed period. The sink node may be fixed or movable. If it is possible to move, add a position measurement function such as GPS, and move to the center or near the center of the area you want to cover as much as possible so that the maximum distance from all sensor nodes is uniform in all directions. Also good.

In addition, the sensor node or the wireless node of the present embodiment can be realized by a computer and a program as well as by realizing the function of the sensor node or the wireless node in hardware. The program is provided by being recorded on a computer-readable recording medium such as a magnetic disk or a semiconductor memory, and is read by the computer at the time of starting up the computer and the computer is controlled by controlling the operation of the computer. Alternatively, it functions as a wireless node.

Next, a second embodiment of the present invention will be described with reference to FIG. FIG. 14 is a block diagram showing the configuration of the network system in the present embodiment. In the present embodiment, an outline of the network system described above will be described.

As shown in FIG. 14, the network system in the present embodiment includes a plurality of nodes 100 including communication means 110 and moving means 120, and each node 100 communicates while moving using moving means 120. A cluster composed of two or more nodes 100 by searching for other neighboring nodes 100 capable of communication by means 110 and combining the searched other nodes 100 with an interval satisfying a predetermined condition. The structure of generating is adopted. In addition, each node 100 configuring the cluster maintains another coupled state of the coupled nodes 100, and other neighboring nodes 100 that can communicate with the communication unit 110 while moving using the moving unit 120. And the other node 100 that has been searched is combined with an interval that satisfies the predetermined condition.

Each node 100 has a configuration including a sensor.

Further, in the network system, each node 100 holds a density value corresponding to the number of other nodes 100 coupled to the own node 100, and simultaneously searches for a plurality of other nodes 100 that can communicate with the communication means. In this case, a configuration is adopted in which the node is coupled to another node 100 that holds a larger density value.

Further, in the above network system, when the number of other nodes 100 coupled to the own node 100 is two or more, each node 100 has the smallest sum of density values among the two or more other nodes 100 coupled. A configuration is adopted in which movement control is performed in which the direction in which the curvature of the arc formed by the two other nodes 100 and the own node 100 is minimized is the movement direction.

Further, in the network system, each node 100 performs the movement control in which the direction in which the curvature of the arc formed by the two other nodes 100 and the own node 100 is the minimum is the movement direction. When the density value of at least one other node 100 of the two other nodes 100 is a density value indicating that the number of other nodes 100 to be combined is one, the moving direction of the own node 100 Is reversed 180 degrees, and a movement control is performed in which the moving direction is a direction in which the curvature of the arc formed by the two other nodes 100 and the own node 100 is maximized.

Further, in the network system, when each node 100 cannot move in the direction in which the curvature of the arc formed by the two other nodes 100 and the own node 100 is minimized, the movement direction of the own node 100 is changed. A configuration is adopted in which the movement control is performed so that the direction of rotation is the direction in which the curvature of the arc formed by the two other nodes 100 and the node 100 is maximized.

In the network system, when each node 100 is not coupled to another node 100 at all, or when coupled to only one other node 100, the moving means 120 performs two-dimensional randomness. The structure is to walk.

Further, the network system adopts a configuration in which the interval that satisfies the predetermined condition is an interval that is determined depending on the communicable distance of each node 100.

Further, the network system adopts a configuration in which the interval satisfying the predetermined condition is an interval determined depending on the size of the sensing area of the sensor provided in each node 100.

In addition, a network system construction method according to another embodiment of the present invention, which is executed when the network system described above operates, constructs a network system composed of a plurality of nodes having communication means and movement means. A method,
Each node searches for other neighboring nodes capable of communicating by the communication means while moving using the moving means, and joins the searched other nodes with an interval satisfying a predetermined condition. Creates a cluster consisting of two or more nodes,
Each node constituting the cluster searches for another node in the vicinity that can communicate with the communication unit while moving using the moving unit while maintaining the coupled state of the coupled nodes. Combine with the searched other nodes while maintaining an interval satisfying the predetermined condition.
The structure is taken.

Further, the above network system construction method adopts a configuration in which each node includes a sensor.

Further, in the above network system construction method, each node holds a density value according to the number of other nodes coupled with the own node, and when simultaneously searching for other nodes that can communicate with the communication means, A configuration is adopted in which it is combined with another node that holds a larger density value.

Further, in the above network system construction method, each node has 2 with the smallest sum of density values among the two or more other nodes coupled when the number of other nodes coupled to the own node is two or more. A configuration is adopted in which movement control is performed in which a direction in which the curvature of an arc formed by two other nodes and its own node is minimized is the movement direction.

Further, in the above network system construction method, each node performs the above-described movement control with the direction of movement in which the curvature of the arc formed by the other two nodes and the self node is minimized. When the density value of at least one other node of the two other nodes is a density value indicating that the number of other nodes to be coupled is one, the moving direction of the own node is reversed by 180 degrees. A configuration is adopted in which movement control is performed in which the direction in which the curvature of the arc formed by the two other nodes and the own node is maximum is the movement direction.

Further, in the network system construction method, when each node cannot move in the direction in which the curvature of the arc formed by the two other nodes and the self node is minimized, the movement direction of the self node is set to 180 degrees. Inverted, a configuration is adopted in which movement control is performed in which the direction in which the curvature of the arc formed by the two other nodes and the self node becomes maximum is the movement direction.

According to another aspect of the present invention, there is provided a node device including a communication unit, a moving unit, and a control unit, wherein the communication device moves while using the moving unit under the control of the control unit. By searching for other neighboring nodes that can communicate by means, and combining with the searched other nodes while maintaining a predetermined condition, a cluster composed of two or more nodes is generated, Further, while searching for another node in the neighborhood that can communicate with the communication means while moving using the moving means while maintaining the connected state of the connected nodes, the other nodes searched And the above-mentioned predetermined conditions are maintained.

Further, the above node device has a configuration including a sensor.

In addition, the above node device holds a density value according to the number of other nodes coupled to its own node, and holds a larger density value when a plurality of other nodes capable of communication by the communication means are simultaneously searched. It adopts a configuration that connects with other nodes.

Further, in the above node device, when the number of other nodes coupled to the own node is two or more, among the two or more other nodes coupled to the node device, two nodes having the smallest sum of density values are compared with the other nodes. A configuration is adopted in which movement control is performed in which the direction of curvature of the arc formed by the nodes is the minimum in the movement direction.

Further, in the node device, even after performing movement control in which the direction of curvature of the arc formed by the two other nodes and the self node is the minimum, the movement of the two other nodes When the density value of at least one of the other nodes is a density value indicating that the number of other nodes to be combined is one, the moving direction of the own node is reversed by 180 degrees, and the two other nodes A configuration is adopted in which movement control is performed in which the moving direction is the direction in which the curvature of the arc formed by the node and the own node is maximized.

Further, in the node device, when the curvature of the arc formed by the two other nodes and the own node cannot be moved in the minimum direction, the moving direction of the own node is reversed by 180 degrees, A configuration is adopted in which movement control is performed in which the direction in which the curvature of the arc formed by the other node and the own node is maximum is the movement direction.

Further, the above-described node device can be realized by incorporating a program into a computer. Specifically, the program according to another aspect of the present invention can communicate with the communication means while moving a computer constituting a node device including the communication means and the movement means using the movement means. By searching for other neighboring nodes and joining the searched other nodes with an interval that satisfies a predetermined condition, a cluster composed of two or more nodes is generated. While searching for another node in the neighborhood that can communicate with the communication means while moving using the moving means while maintaining the combined state of It is made to function as a control means for performing control for coupling while maintaining a satisfying interval.

Even the invention of the network system construction method, the node device, or the program having the above-described configuration has the same operation as the above-described network system, and thus the above-described object of the present invention can be achieved.

Although the present invention has been described with reference to the above embodiments, the present invention is not limited to the above-described embodiments. Various changes that can be understood by those skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention.

Note that the present invention enjoys the benefit of the priority claim based on the patent application of Japanese Patent Application No. 2008-291736 filed on November 14, 2008 in Japan, and is described in the patent application. The contents are all included in this specification.

DESCRIPTION OF SYMBOLS 10 ... Sensor node 11 ... Sensor function part 12 ... Wireless communication function part 13 ... Movement function part 14 ... Memory | storage part 15 ... Control part

Claims (22)

A network system comprising a plurality of nodes provided with communication means and movement means,
Each node searches for other neighboring nodes capable of communicating by the communication means while moving using the moving means, and joins the searched other nodes with an interval satisfying a predetermined condition. Creates a cluster consisting of two or more nodes,
Each node constituting the cluster searches for another node in the vicinity that can communicate with the communication unit while moving using the moving unit while maintaining the coupled state of the coupled nodes. A network system, characterized in that the network system is coupled with the searched other node while maintaining an interval satisfying the predetermined condition. The network system according to claim 1, wherein each node includes a sensor. Each node holds a density value according to the number of other nodes coupled with its own node, and when a plurality of other nodes capable of communication by the communication means are simultaneously searched, other nodes holding a larger density value The network system according to claim 1, wherein the network system is coupled to a node. When each node has two or more other nodes coupled to the own node, among the two or more other nodes coupled, the two other nodes having the smallest sum of density values and the own node The network system according to claim 3, wherein movement control is performed such that a direction in which a curvature of a formed arc is minimum is a movement direction. Each node has at least one of the two other nodes even after performing movement control in which the direction of curvature of the arc formed by the two other nodes and its own node is minimized. When the density value of one other node is a density value indicating that the number of other nodes to be combined is one, the moving direction of the own node is reversed by 180 degrees, 5. The network system according to claim 4, wherein movement control is performed such that a direction in which a curvature of an arc formed by the nodes is maximum is a movement direction. If each node cannot move in the direction in which the curvature of the arc formed by the two other nodes and its own node is minimized, it reverses the movement direction of its own node by 180 degrees, and the two other nodes 6. The network system according to claim 4, wherein movement control is performed such that a direction in which a curvature of an arc formed by the own node is maximum is a movement direction. 2. A two-dimensional random walk is performed by the moving means when each node is not coupled to any other node at all or when coupled to only one other node. The network system according to any one of 1 to 6. The network system according to any one of claims 1 to 7, wherein the interval satisfying the predetermined condition is an interval determined depending on a communicable distance of each node. The network system according to any one of claims 1 to 7, wherein the interval satisfying the predetermined condition is an interval determined depending on a size of a sensing area of a sensor included in each node. A method of constructing a network system composed of a plurality of nodes provided with communication means and movement means,
Each node searches for other neighboring nodes capable of communicating by the communication means while moving using the moving means, and joins the searched other nodes with an interval satisfying a predetermined condition. Creates a cluster consisting of two or more nodes,
Each node constituting the cluster searches for another node in the vicinity that can communicate with the communication unit while moving using the moving unit while maintaining the coupled state of the coupled nodes. Combine with the searched other nodes while maintaining an interval satisfying the predetermined condition.
A network system construction method characterized by the above. The network system construction method according to claim 10, wherein each node includes a sensor. Each node holds a density value according to the number of other nodes coupled with its own node, and when a plurality of other nodes capable of communication by the communication means are simultaneously searched, other nodes holding a larger density value Join with nodes,
The network system construction method according to claim 10 or 11, characterized in that When each node has two or more other nodes coupled to the own node, among the two or more other nodes coupled, the two other nodes having the smallest sum of density values and the own node Performing movement control in which the direction of curvature of the formed arc is the minimum,
The network system construction method according to claim 12. Each node has at least one of the two other nodes even after performing movement control in which the direction of curvature of the arc formed by the two other nodes and its own node is minimized. When the density value of one other node is a density value indicating that the number of other nodes to be combined is one, the moving direction of the own node is reversed by 180 degrees, Performs movement control with the direction of movement that maximizes the curvature of the arc formed by the nodes as the movement direction.
The network system construction method according to claim 13. If each node cannot move in the direction in which the curvature of the arc formed by the two other nodes and its own node is minimized, it reverses the movement direction of its own node by 180 degrees, and the two other nodes And movement control with the moving direction as the direction in which the curvature of the arc formed by the own node is maximum,
15. The network system construction method according to claim 13 or 14, A node device comprising a communication means, a movement means, and a control means, and under the control of the control means, searches for other nearby nodes that can communicate with the communication means while moving using the movement means. Then, a cluster composed of two or more nodes is generated by maintaining an interval satisfying a predetermined condition with the searched other nodes, and further, while maintaining the connection state between the combined nodes, Searching for another node in the neighborhood that can communicate with the communication unit while moving using the moving unit, and combining the searched other node with an interval that satisfies the predetermined condition. A node device characterized by the above. The node device according to claim 16, further comprising a sensor. The density value corresponding to the number of other nodes coupled to the own node is held, and when a plurality of other nodes capable of communicating by the communication means are simultaneously searched, the node is coupled to another node holding a larger density value. The node device according to claim 16 or 17, characterized in that: When the number of other nodes coupled to the own node is two or more, among the two or more other nodes coupled to each other, an arc formed by the two other nodes having the minimum density value and the own node The node device according to claim 18, wherein movement control is performed such that a direction in which the curvature of the movement is minimum is a movement direction. Even after performing the movement control in which the direction of curvature of the arc formed by the two other nodes and the self node is the minimum, the at least one other of the two other nodes When the density value of the node is a density value indicating that the number of other nodes to be combined is one, the moving direction of the own node is reversed by 180 degrees, and the two other nodes and the own node are formed. The node device according to claim 19, wherein movement control is performed such that a direction in which a curvature of a circular arc is maximized is a movement direction. When the curvature of the arc formed by the two other nodes and the own node cannot be moved in the minimum direction, the moving direction of the own node is reversed by 180 degrees, and the two other nodes and the own node are 21. The node device according to claim 19 or 20, wherein movement control is performed such that a direction in which a curvature of the arc formed by the maximum is a movement direction is set. A computer that constitutes a node device including a communication unit and a moving unit is searched for other nearby nodes that can communicate with the communication unit while moving using the moving unit, and the other nodes searched And a cluster composed of two or more nodes by combining them while maintaining an interval satisfying a predetermined condition, and further using the moving means while maintaining the combined state of the connected nodes. While searching for another node in the vicinity that can communicate with the communication unit, the control unit functions as a control unit that performs control for coupling with the searched other node while maintaining an interval that satisfies the predetermined condition. Program for.

Images