Distributed organization of sensor networks

Description

The present invention relates to the distributed organization of sensor networks as are, for example, employed in disaster control, meteorology or when observing plants and animals in biotopes.

Today, sensor networks are employed in many fields. Fields of application are, for example, observing climatic changes, air pollution, establishing spatially and temporally resolved temperature or humidity profiles, weather forecast and observation, observation of plants and animals in biotopes, disaster control, etc. Sensor networks are computer networks, the task of which is detecting measuring data and which in the ideal case form and administer themselves autonomously. The parties in such a network, so-called sensor nodes, are battery-operated miniature computers which communicate with one another via a radio interface and receive measuring values via a plurality of sensors. Thus, the measuring values are not sent directly from each sensor node to a base station (also referred to as evaluating station) , but are taken up by other sensor nodes before the data are passed on towards the base station. This method is also referred to as multi- hop method since a signal is carried across several network nodes before it reaches its destination, namely the base station. It serves for bridging transmission links which could not be used with a direct connection due to an insufficient range of the radio interfaces used.

Thus, the transmission links on which the sensor nodes transmit the data towards the base station are recalculated and adjusted when the network is operated. The administration of networks of this kind, such as, for example, the allocation of addresses, radio resources and setting transmission links within a network, is performed

here by a central network node, namely the base station. Due to their easy handling and cheap operation, these networks are considered to be alternatives for wired solutions. A great advantage compared to conventional solutions is the fact that existing systems may be extended easily. When adding further sensor nodes, not only is the spatial resolution of the measurement increased, but also fail-safety of the network is improved, since measuring values can now reach evaluation by additional links. Sensor networks are successfully employed in many fields, like in environmental technology. Generally, the increased usage of sensor networks is expected to provide improved scientific understanding of environmental processes. Ecosystems can be observed in greater detail and over a longer period of time than is possible by conventional systems. Greater regions can be monitored using the multi-hop method and the data can be sent to the users over greater distances.

Sensor networks may be employed in fields in which earthquakes, forest fires, flooding or volcanic eruptions are likely to occur. Motion, smoke or humidity sensors can be employed correspondingly in order to recognize possible dangerous situations in good time.

Sensor networks are also suitable for everyday tasks. A house equipped with sensor networks would be able to optimize its energy consumption due to the environmental conditions and light conditions observed. Electrical devices and light sources could be switched off automatically as soon as the inhabitant has not stayed in certain rooms for a certain period of time.

Like conventional computer networks, sensor networks are subdivided logically by the protocols used. Currently usable sensor networks, such as, for example, TinyOS developed by the "University of California" in Berkeley, or sensor networks operating according to the ZigBee standard by the ZigBee Alliance, require sensor nodes performing a

pre-programmed function to maintain the sensor network. If such a sensor node fails in operation, this will put the perfect functioning of the network at risk. A disadvantage of this technology is that when such a pre-programmed sensor node fails, all the sensors coupled to this sensor node and maybe further pre-programmed sensor nodes may lose connection to the base station, and this may trigger failure of entire network branches.

This is particularly true for the base station of such a sensor network. In the context of networks of this kind, this is referred to as a hierarchical network structure, as is exemplarily illustrated in Fig. 5. Fig. 5 shows a schematic hierarchical network structure consisting of a base station 500 (BS), several sensor nodes 510 (SN) and many sensors 520 (S) . In such a hierarchical network, administering tasks, such as, for example, administering addresses of the individual sensor nodes, are performed by the base station, however a sensor node does this for the individual sensors. If a single sensor node fails, the connection to all the sensors and sensor nodes below these sensor nodes will be lost. If a base station fails, this will be equivalent to a complete network failure. In the case of the base station, this is said to be a "single point of failure", since the function of the entire network depends on the function of the base station. Apart from the task of collecting the measuring values from the network and making same available to the user, the base station controls and regulates the setup of a sensor network. A failure of the base station is equivalent to the entire network failing.

Starting from this prior art, it is the object of the present invention to provide an improved concept for operating sensor networks, by means of which higher reliability can be achieved.

- -

This object is achieved by a device according to claim 1 and a method according to claim 17.

The central idea of the present invention is to set up a network from a plurality of network nodes which have equal rights in that theoretically every one may function as a cluster head. Sub-regions of the network are combined to form clusters of network nodes and there is, in every cluster of network nodes, a cluster head, the functionality of which may be taken over by any network node of the cluster. A base station which now only has the function of acquiring data may gain access to the entire data of the network at any network node. The communication in the inventive network between the individual network nodes takes place via a communication interface, such as, for example, a radio or infrared interface. The present invention allows decentralizing the administering tasks in a network such that the central role of an administering node can be abandoned.

According to the invention, this is achieved by a data- processing device representing a network node in a network and the network, except for a base station, being set up exclusively of inventive devices. The inventive device comprises communication means implemented to communicate with other data-processing devices. The communication between the data-processing devices here refers to both the organization of the network and to collecting and passing on data which are exemplarily acquired by optional measuring means. For this, the data-processing device comprises control means implemented to try, via the communication means, to contact other data-processing devices, to initiate, in the case of no response or a response indicating that there is no possibility of joining an existing cluster of data-processing devices, a cluster as cluster head and to administer this cluster. In the case of a response indicating that there is a possibility of

- -

joining an existing cluster, the data-processing device is implemented to join the cluster as a cluster member.

The network consists of clusters of sensor nodes. A cluster of sensor nodes is characterized in that there is one sensor node within the luster, the so-called cluster head performing the cluster administration. The administration of the cluster exemplarily includes the cluster head storing identification numbers of all cluster members and the identification numbers of all neighboring clusters. Every sensor node and every cluster has an unambiguous identification. In contrast to conventional sensor networks, all sensor nodes in the inventive solution are implemented equally in that every sensor node may take over the role of a cluster head. Individual sensor nodes taking part in the sensor network try to register with a cluster head in the surroundings. For this, for example when starting up, they send a request signal and wait for a response. Cluster members pass on request signals received to their cluster heads, the cluster heads process the request signals received and send a response to the request signals, maybe again via their cluster members (multi-hop method) to the requesting sensor node. In this way, the cluster head can push the setup of the network specifically and adjust same to the resources (storage, computing power, etc.) available. The unambiguous identification of cluster members here can be stored in the respective cluster head and serve as the basis for entering a cluster.

The cluster heads communicate among one another so that the actual network structures are stored in a distributed form on the cluster heads. Should a sensor node not be able to join a cluster because its request signal remains unanswered or it only receives negative replies, exemplarily because a cluster head cannot accept new cluster members in its cluster due to lacking transmission resources, this sensor node will form a new cluster in which it may function itself as a cluster head and

establish a cluster identification for this cluster, exemplarily based on its own unambiguous identification. The cluster identification may be based on the unambiguous identification of the cluster head.

Thus, the base station has lost its central role when forming and administering a sensor network and is only be required to acquire data. It will behave like a simple sensor node and will register with a cluster in its surroundings. When registering the base station with a cluster, the cluster head initiates data to be passed on to the base station. A cluster member signalizes to its cluster head that a base station has registered and passes on the requests of the base station to the cluster head or passes on the requests of the cluster head to the base station. The cluster member then acts as a switching center between the base station and the cluster head. This functionality does not only relate to requesting a base station, but generally the cluster members pass on internal and external requests to cluster heads (such as, for example, requests by new sensor nodes, data requests, measuring data, routing information, etc.). One way of realizing this is the cluster heads giving specific instructions to the individual cluster members as to the timeframe and which sensor nodes (routing setting) a request is to be passed on to (multi-hop method) . Another way would be for the cluster members to form their own routing maps based on information of their neighboring data-processing devices or based on information a cluster head distributes within a cluster.

Both the data of its own cluster and the data of other clusters are sent to the base station. Should a base station fail, this will be determined by the cluster head in charge and communicated to the other sensor nodes involved. The cluster head in charge is that cluster head with which the base station has registered directly or indirectly (via a cluster member of its cluster). Thus,

applications may be realized in which the sensor network has to be operated without a base station over a long period of time (like, for example, in logistics, goods tracking, etc . ) .

Should a cluster head fail, the cluster administered will break down into individual sensor nodes which will then try to register with the closest cluster or initiate a cluster on their own.

A great advantage of the inventive device is high robustness against base station failure. Whereas conventional methods for forming a network necessarily require a base station for administration to be able to establish a network structure, an inventive sensor network organizes itself without requiring a central administering node. The administering tasks are distributed to the sensor nodes and/or cluster heads present in the sensor network. Should a cluster head fail in the inventive network, its functionality may be taken over by any other sensor node. A centralization of administering tasks (single point of failure) is thus ruled out. Applications of highly mobile sensor networks are thus made easier or made possible at all. Tracking different goods in logistics is an example of this.

Preferred embodiments of the present invention will be detailed subsequently referring to the appended drawings, in which:

Fig. 1 shows a fundamental block diagram with functional blocks of an inventive embodiment;

Fig. 2 is a schematic illustration of a realization of a network before a cluster has formed;

Fig. 3 is a schematic illustration of a realization of a network after the cluster has formed;

Fig. 4 is a schematic illustration of a realization of a network during data transmission to a base station; and

Fig. 5 is a fundamental illustration of a hierarchical network structure according to the prior art.

Subsequently, the preferred embodiment of a network consisting of inventive devices for decentralizing the network administration will be described in greater detail referring to Figs. 1-4. At fist, the setup of an inventive device will be discussed exemplarily referring to Fig. 1.

Fig. 1 shows the fundamental setup of an inventive data- processing device 100. The inventive device 100 comprises communication means 110 and control means 120. The communication means 110 and the control means 120 are implemented to exchange control data between each other. The control means 120 thus tries to contact other inventive devices via the communication means 110. Should the control means 120 not receive a response of other inventive devices within reach via the communication means 110 or receive a response indicating that there is no possibility of joining an already existing cluster of inventive data-processing devices, the data-processing device 100 will take over the role of a cluster head. The cluster head thus is implemented to administer a cluster of data-processing devices, wherein the cluster head stores the unambiguous identification numbers of every cluster member, of directly neighboring data-processing devices and neighboring clusters, wherein directly neighboring data-processing devices are those to which there is a direct connection. In addition, the cluster head exemplarily establishes a cluster identification based on its own unambiguous identification. Additional administering tasks for the cluster heads may, for example, be establishing routing maps in which the cluster head establishes via which

cluster members it can communicate to the other cluster heads or, exemplarily, even the administration of the cluster size which may depend on parameters, such as, for example, availability of network resources (exemplarily bandwidth) . Should the control means 120, via the communication means 110, receive a response indicating that there is a possibility of joining a cluster already existing, the inventive data-processing device will join a cluster as a cluster member. The cluster member thus is implemented to store the unambiguous identification numbers of directly neighboring data-processing devices and their clusters .

The administration of a cluster may include further functions, such as, for example, coordination of data transmissions to a base station. In such a case, it is the task of the cluster heads to give their individual cluster members instructions for transmitting data (exemplarily measuring data) in a coordinated manner and pass same on to the base station. Thus, a timeframe and a route

(transmission path in the network) via certain network nodes may exemplarily be preset by the cluster head. Routes may, for example, already be determined beforehand by cluster heads and stored in maps, and it would also be conceivable for the cluster members to store routes to other cluster heads in maps to achieve faster data transmission .

Subsequently, starting from Figs. 2 and 3, the formation of a network having two clusters will be discussed. Fig. 2 shows a schematic illustration of inventive devices 1-9 which will subsequently be referred to as sensor nodes or network nodes, in a network in the starting situation.

Apart from communication and control means, sensor nodes additionally comprise measuring means detecting measuring data of a physical quantity stored in the data-processing device. The measuring data are then fetched from a base

station, i.e. they are transmitted from the entire network to the base station. The sensor nodes in the inventive network are identical in that they comprise the structure shown in Fig. 1. In addition, they may comprise other features which are different. Exemplarily, they may comprise different measuring means for acquiring measuring data of different physical quantities. A base station, too, comprises at least the structures illustrated in Fig. 1 so that it can communicate with any cluster member or cluster head. However, the base station has to perform the additional function of acquiring data and for this reason it is additionally implemented to pass corresponding instructions to the network and to receive the data.

In Fig. 2, every sensor node 1-9 is illustrated as a circle and given a number for identification. The lines represent the physical ways of connecting the individual sensor nodes among one another. Exemplarily, in Fig. 2 sensor node 4 may set up a direct connection to sensor nodes 2, 3 and 8, and in order to set up a connection to the sensor node 7 the sensor node 4 would have to communicate indirectly via one of sensor nodes 2 or 3. This may, for example, be established in a routing map.

In this schematic scenario, two clusters form, as is illustrated in Fig. 3, exemplarily sensor nodes 4 and 5 each become a cluster head 320. Fig. 3 shows the clusters formed in respective circles 300 and 310 indicated in broken lines and the respective cluster heads 320 are identified by bold circles. The clusters 300 and 310 are formed as follows:

After switching on, every sensor node 1-9 checks whether other sensor nodes are in its surroundings. For this, it emits a request signal and waits for a reply from existing clusters and/or cluster heads.

If this is not the case, this sensor node will declare itself cluster head 320 and accept from then on requests and registerings of other sensor nodes. This means that when receiving a request from a sensor node in the future it will admit it to its cluster provided the resources of the clusters heads allow it.

If a cluster has already formed in its surroundings, the sensor node will try to join it as a cluster member. After joining successfully, it will automatically pass on requests and registerings to its cluster head. If, for example, the request signal of a new sensor node is received, the cluster member will pass it on to the cluster head on the one hand and, on the other hand, pass on the responses of the cluster head to the requesting sensor node (multi-hop method) .

- If registering with a cluster fails, exemplarily because the cluster head of this cluster does not have sufficient resources, the sensor node will form a new cluster and function as a cluster head. Exemplarily, it would be conceivable for the cluster head only to have at its disposal a finite number of communication channels and not to accept any additional cluster members should these be occupied sufficiently.

The decision on whether a cluster head will accept the request of a sensor node or not may depend on several factors. Exemplarily, a maximum cluster size may be preset in a realization or result from memory and/or calculating limits or other limited resources of the cluster head. Another inventive realization may, for example, make the maximum cluster size dynamically depend on the resources used, exemplarily the spatial distance of the cluster members may have an effect on the transmitting power of the

cluster head available and the maximum cluster size may depend on the transmitting power of the cluster head still available.

In this way, the network forms any number of clusters. The administration and setup of such a sensor network are taken over by the cluster heads only. The registering of a base station to transmit data to a cluster triggers an automatic passing on of data packets to the base station over the entire network.

Fig. 4 is an exemplary illustration of such a scenario. Fig. 4 again shows the network of Figs. 2 and 3, wherein a base station 400 registers with the cluster head 4 to retrieve measuring data from the sensor network. In Fig. 4, the path of the data packets from the sensor node 1 to the base station is illustrated specifically. The arrows 410 indicated thus represent the path of the data packets. This path may, for example, be written down in a routing map in the cluster head 4. This would mean that a cluster head, apart from the neighboring cluster identification, also stores information on the path to the cluster head of the neighboring cluster to pass on, in the case of polling measuring data, stored routes to its cluster members and thus to coordinate same. In addition, a cluster head may also store several routes to neighboring cluster heads to realize parallel routes and thus higher transmission rates. In principle, many variations of establishing a route are possible. A simple variation would, for example, be for the sensor nodes searching for a certain node to pass on a search message to all their neighbors, and thus a sensor node to be searched is searched iteratively in the entire network.

It can be seen in Fig. 4 that the data packets are at first passed on from the sensor node 1 to the sensor node 9, for there via the sensor node 6 to the sensor node 8 and finally via the cluster head 4 to the base station. The

data transmission is coordinated by the cluster heads 4 and 5. The cluster head 4 at first passes the data request of the base station 400 on to the neighboring cluster of the cluster head 5. The cluster head 5 then causes cluster member 1 to pass on the requested data in the manner described to the base station. Thus, it is conceivable that the route has already been established and stored in the cluster head 5 and that same passes on the route to the cluster member 1. Another variation would be that the route has already been stored in cluster member 1 or that, exemplarily, the cluster member simply passes on the data to all its neighbors until they reach the base station iteratively .

In summary, it can be noted that the inventive realization of a sensor node and a sensor network offer decisive advantages compared to conventional networks. By means of decentralizing the administering tasks, such as, for example, address administration and the administration of network resources, a considerably improved robustness compared to conventional networks is achieved. The network resources to be administered thus are dependent on the communication interface of the inventive device. Exemplarily, in infrared interfaces the direct line-of- sight connection and the spatial distance play important roles, whereas in radio interfaces the transmitting power available and the number of transmitting channels play important roles.

It is particularly uncomplicated and cheap to extend the network due to the ability of the individual sensor nodes to function both as cluster members and cluster heads. A dependence on a central network node, like in conventional network structures is the case for the base station, is strictly avoided by the present invention.

Depending on the circumstances, the inventive method may be implemented in either hardware or software. The

implementation may be on a digital storage medium, in particular on a disc or a CD having control signals which may be read out electronically which can cooperate with a programmable computer system such that the corresponding method will be executed. Generally, the invention thus also is in a computer program product having a program code stored on a machine-readable carrier for performing the inventive method when the computer program product runs on a computer. Put differently, the invention may thus also be realized as a computer program having a program code for performing the method when the computer program runs on a computer .