WO2012009849A1

WO2012009849A1 - A routing scheme for wireless sensor networks

Info

Publication number: WO2012009849A1
Application number: PCT/CN2010/075286
Authority: WO
Inventors: Canfeng Chen; Jian Ma; Chengcheng Long
Original assignee: Nokia Corporation
Priority date: 2010-07-20
Filing date: 2010-07-20
Publication date: 2012-01-26

Abstract

The present invention proposes a routing scheme for networks, especially for a wireless sensor networks. With the invention, an end-to-end path can be built, and then a lightweight streaming data dissemination scheme for wireless sensor networks with mobile sinks is obtained. The proposed method comprising: flooding a message within limited hops to discover at least one data processing apparatus of a network; in response to said flooding, receiving at least one reply; if there is no reply coming from a data processing apparatus, transmitting at least one request to an intermediate apparatus from which the reply is sent, to discover at least one data processing apparatus with the routing information maintained by the intermediate apparatus.

Description

A routing scheme for wireless sensor networks

Field of the Invention

The present invention relates to the field of communication, and more particularly to a routing scheme for networks, especially for wireless sensor networks.

Background of the Invention

In should be noted that this section introduces contents that may help facilitate a better understanding of the invention, but the statements thereof should not be considered as admissions about what is prior art or what is not prior art.

Wireless sensor networks (WSNs) have attracted intensive attention in recent years due to their wide variety of potential applications. A sensor network always consists of spatially distributed autonomous sensor nodes and sink nodes, to cooperatively monitor physical or environmental conditions (such as temperature, sound, vibration, pressure and pollutants), and capture events of interest (such as object tracking, event monitoring). Recent developments in digital circuitry, wireless communication, and Micro Electro-Mechanical Systems (MEMS), have made possible that multifunctional senor nodes, such as image sensor, audio sensor, and video sensor or the like, reflect and describe the physical phenomenon. An example is the SenseCam made by Microsoft, which can provide the information which cannot be easily described by simple sensor node.

Here we use streaming data to represent a sequence/number of data packets waiting for transmission in a sensor node. It is believed that streaming data transmission will be a very common situation for wireless sensor networks, such as for audio, image, and video sensor nodes, which can dramatically enhance the event description in wireless sensor networks. Another situation is that a bunch of buffered sensor data which are collected for a certain time period waiting for transmission. As sensor data usually needs to be disseminated from the source sensors to sink nodes, thus data dissemination is one of the fundamental problems in WSNs. In addition, as these sensors usually operate on limited non-rechargeable battery power and are expected to last over several months or years, energy efficiency becomes one of the most critical design issues for WSNs.

In the past several years, researchers have proposed to exploit the mobility of sinks for energy efficient data dissemination in WSNs. Especially, employing existing mobile objects, such as mobile handsets and vehicles to collect sensor data attracts a lot of attention. However, finding the routing path for disseminating data to such mobile objects is a challenging issue due to the random/uncontrollable/unpredictable mobility of such mobile objects. For existing proposed data dissemination protocols in wireless sensor networks with mobile sinks, energy efficiency of transmitting the streaming data is low.

The existing solutions on data dissemination in WSNs with mobile sink can be classified into four categories based on how to disseminate data to sinks: (1 ) flooding or hierarchical flooding approach; (2) position estimation based on geographic routing approach; (3) controlled sink mobility approach; and (4) opportunistic forwarding approach.

(1 ) Flooding or hierarchical flooding approach

The straightforward way to provide data dissemination to mobile sinks is through the flooding. With this approach, the data packet is sent throughout the network, and every node that receives this packet forwards it to the immediate neighbouring nodes. However, this naive approach is too costly for the resource constrained WSNs since a large number of duplicated data packets are sent. Another naive approach is to periodically flood the location information of mobile sinks to find the path between the data source and the mobile sink. Obviously, it will also drain much energy of sensor nodes.

Directed Diffusion (DD) is also a flooding based approach. The sink floods interests for desired data. When some nodes sense the data matching the interests, they send the data back to the sink with a low data reporting rate along the reverse paths of cached interests.

The major problem in the flooding approach is that it costs too much energy. To alleviate the overhead of whole network flooding, hierarchical structure for data dissemination was proposed, wherein flooding only occurs among backbone/partial nodes, such as Two-Tier Data Dissemination (TTDD), Scalable Energy-efficient Asynchronous Dissemination (SEAD), Hierarchical Cluster-based Data Dissemination (HCDD), etc. However, for the hierarchical flooding approach, as the network size increases, the flooding overhead is still high. Besides, the construction of the hierarchical structure also incurs energy cost. So, the problem for the hierarchical flooding approach is the poor scalability.

(2) Position estimation based on geographic routing approach

A more efficient approach to find the paths between data sources and mobile sinks is the position estimation approach, such as Query Based Data Collection (QBDCS). Assume the motion trajectory of mobile sinks can be predictable in a short period, e.g., a vehicle moves along the road and the digital map is available, the prediction of its future mobility becomes possible. Another assumption is that all nodes know their location information and where the destination is. Thus, for the source node, since it knows the mobility information of the mobile sink, it can estimate the mobile sink's instantaneous position; hence it can disseminate data to the mobile sink using geographic routing protocol. The position estimation approach relies on the sensor's location information. However, the location and mobility information may not be always available in many practical situations, because it is heavily power-consumed to equip expensive GPS devices in the cheap sensor nodes.

(3) Controlled sink mobility approach

Some existing work proposes to use dedicated mobile robots for collecting sensed data. To optimize the network performance such as improving the energy efficiency, the motion trajectory of mobile sinks is always carefully designed and controlled. However, in real-world scenarios, mobile sinks are more likely to be the combination of data collection devices and existing mobile objects with random mobility, e.g., mobile handsets, notebooks or vehicles.

(4) Opportunistic forwarding approach

Another alternative solution is the opportunistic forwarding, where the collected data is often delay tolerant, i.e., its delivery to the sinks is not time critical, e.g., Data Mobile Ubiquitous LAN Extensions (MULEs) and Transmission Scheduling Algorithm for wireless Sensor Networks with Mobile Sinks (TSA-MSSN). The basic strategy only allows data delivery when sensors are in direct proximity of the mobile sink and this technique has very little communication overhead. The disadvantage is obvious, i.e., it may experience very long delivery delay, a few hours or even days.

In fact in the WSNs research field, there is not much work on the streaming data dissemination in WSNs with sink (especially with mobile sink) till now. In addition, most of the existing schemes are based on the geographical greedy forwarding, or focus on the data dissemination to static sink.

Therefore, an efficient solution on data dissemination is required. This invention designs an efficient routing solution for networks, especially for WSNs. Using such routing solution, a lightweight scheme for disseminating streaming data to a mobile sink is obtained, without the knowledge of any node's or sink's location information and avoid the high cost of global flooding of sink's mobility information throughout the network at the same time.

Summary

The invention aims to find a path with which a bunch of data packets can be disseminated to a data processing apparatus. The following routing method, apparatus and corresponding computer programs are proposed to solve or at least alleviate at least one of the existing problems.

According to one aspect of the invention, a method, comprising: flooding a message within limited hops to discover at least one data processing apparatus of a network;

in response to said flooding, receiving at least one reply;

if there is no reply come from a data processing apparatus, transmitting at least one request to an intermediate apparatus from which the reply is sent, to discover at least one data processing apparatus with the routing information maintained by the intermediate apparatus.

In other words, it means if all the received replies coming from one or more intermediate apparatuses (which maintain related routing information), the request will be transmitted in the above method.

Preferably, the related routing information maintained by an intermediate apparatus is recent.

Optionally, the method can further comprising:

if more than one data processing apparatuses are discovered, selecting at least one preferred data processing apparatus; and/or

if a plurality of replies have been received from more than one intermediate apparatuses, selecting at least one preferred intermediate apparatus to transmit said request.

Optionally, said selecting can be made on the basis of at least one of the following: distance, the cost of energy, the cost of time, security, confidence, the processing and forwarding ability/speed, application-specific preferences/characteristics, whether the maintained routing information is recent.

With the aforementioned methods, an end-to-end path can be built to the discovered data processing apparatus, then data, preferably streaming data can be transmitted to the discovered or selected preferred data processing apparatus.

Preferably, the request is further forwarded by the intermediate apparatus to a data processing apparatus on the basis of its routing information or the combination of its routing information and the moving trajectory of the data processing apparatus.

Preferably, the network is a wireless network or a wireless sensor network, and the data processing apparatus is a mobile sink or a static sink.

Specifically, if the data processing apparatus is a mobile sink, the mobile sink is discovered by the intermediate apparatus based on routing information or routing information in combination with moving trajectory of the mobile sink maintained by the intermediate apparatuses; if the data processing apparatus is a static sink, the mobile sink is discovered based on routing information maintained by the intermediate apparatus directly.

Preferably, upon overhearing, duplicate transmissions of replies and/or requests can be avoided.

Optionally, a discovered data processing apparatus can rebuild a path (to the source flooding the message) through geographic greedy forwarding based on location information.

According to yet another aspect of the invention, an apparatus, comprising

at least one processor; and

at least one memory including computer program code;

the at least one memory and the computer program code are configured to, with the at least one processor, cause the apparatus to perform at least following:

flood a message within limited hops to discover at least one data processing apparatus of a network;

in response to said flooding, receive at least one reply;

if there is no reply come from a data processing apparatus, transmit at least one request to an intermediate apparatus from which the reply is sent, to discover at least one data processing apparatus with the routing information maintained by the intermediate apparatus.

According to yet another aspect of the invention, a method, comprising: receiving a message for discovering a data processing apparatus flooded within limited hops of a network;

transmitting a reply back if routing information relating to a data processing apparatus is maintained;

if a request for discovering a data processing apparatus is feedback, addressing to at least one data processing apparatus with maintained routing information.

With the above method, a path from a source sending the message to the discovered data processing apparatus can be built, and data can be transmitted to the data processing apparatus.

Preferably, the network is a wireless sensor network, and the data processing apparatus is a mobile sink or a static sink; and/or if the data processing apparatus is a mobile sink, it is discovered based on maintained routing information or routing information in combination with its moving trajectory; and/or if the data processing apparatus is a static sink, it is discovered based on maintained routing information directly.

Optionally, said addressing comprising forwarding the feedback request from the intermediate apparatus to a data processing apparatus.

Optionally, if a message sent by the discovered data processing apparatus for rebuilding a path to a source is received, unicasting the received message to the source from which message for discovering a data processing apparatus is flooded; and/or upon overhearing, duplicate transmission of replies and/or feedback requests can be avoided.

According to yet another aspect of the invention, an apparatus, comprising

at least one processor; and

at least one memory including computer program code;

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least following:

receive a message for discovering a data processing apparatus flooded within limited hops of a network;

transmit a reply back if routing information relating to a data processing apparatus is maintained;

if a request for discovering a data processing apparatus is feedback, address to at least one data processing apparatus with maintained routing information.

According to yet another aspect of the invention, a method, comprising determining whether to rebuild a path to a source;

if determine to rebuild a path, flooding from a data processing apparatus a message within limited hops of a network;

wherein the message is further transmitted to the source by an intermediate apparatus with its maintained routing information. Preferably, the intermediate apparatus locates within a limited flooding range of the source in which a message for discovering a data processing apparatus has been flooded.

Optionally, the determination can be made based on the required probability of rebuilding a path, or a path shorter than the current path connecting the source to the data processing apparatus, and/or an energy cost analysis.

Wherein, a path can be built if the flooding hop-count is no less than the difference of hop-count of the current path and the flooding hop-count of the source, or if there is an apparatus locate within the limited flooding range of the source and limited flooding range of the data processing apparatus.

Wherein, the probability of rebuilding a shorter path can be estimated on the trajectory of the current path, or angles of segments of the current path together with location information.

Optionally, the energy cost analysis comprising the energy cost for building a shorter path and/or the energy saving brought out by the shorter path.

Preferably, the energy cost and energy saving can be estimated from the one or more of the following factors maintained by a data processing apparatus or derived/estimated from its maintained routing information with experiences: node density, flooding area, the number of nodes within the flooding rage, the number of paths that the message will be transmitted to the source, the hop-count from the intermediate apparatus to the source, the amount of data to be transmitted from the source to the data processing apparatus, the reduced hop-count by the shorter path comparing with the current path.

Preferably, a method of numerical integration can be used to reduce the computation complexity.

Preferably, upon overhearing, duplicate transmissions can be avoided; and/or an intermediate apparatus overhearing the flooded message can update its related routing information; and/or the message is transmitted unicastly.

Preferably, the flooding of the data processing apparatus can be approximately a circular or fan-shaped region. According to yet another aspect of the invention, an apparatus, comprising

at least one processor; and

at least one memory including computer program code;

determine whether to rebuild a path to a source;

if determine to rebuild a path, flood from a data processing apparatus a message within limited hops of a network;

wherein the message is further transmitted to the source by an intermediate apparatus with its maintained routing information.

According to yet another aspect of the invention, apparatuses comprising respective means for implementing the steps of the above methods or apparatus are proposed.

With the above solutions of the invention, a person skilled in the art understands that a path from a source to the discovered data processing apparatus can be built, and streaming data can be disseminated on this path.

For the invention, the location knowledge of any sensor node or the mobile sink is released, this is especially useful for a mobile sinks as they usually move randomly and unpredictably. The advantages brought out by the invention are obvious as the invention applicable for general and practical application scenarios, where the accurate location information is unavailable. However, it should be noted that this doesn't mean the invention exclude such utilization of location information whenever these location information are available. For example, as more and more mobile devises are equipped with GPS receivers, thus when the mobile sink's location is available, another advantage is that after the Route Rediscovery with chasing mode, a rough estimation on the location of the source can be obtained.

Preferably, existing mobile objects, such as mobile handsets, laptops and vehicles, can be used to collect sensor data. In a preferred embodiment of the invention, such mobile objects can initiate a reroute procedure for building a shorter path. In the latter case, software for implementing the preferred solution can be embodied in the existing mobile objects. With this preferred reroute solution, an efficient path can be built, and lower communication overhead can be achieved.

Simply speaking, the proposed scheme allows a source to select a preferred apparatus for further processing or forwarding its data if multiple apparatuses are available, and also allows a longer distance routing path connecting the source to an discovered apparatus to be redirected to a shorter distance routing path in an energy efficient manner.

Hereinafter, preferred embodiments will be proposed together with appended figures. However, all terms used in the description and the claims are to be interpreted according to their ordinary meaning in the technical field, unless explicitly defined otherwise herein. All references to "a/an/the [apparatus, means, step, etc]" are to be interpreted openly as referring to at least one instance of said apparatus, means, step, etc., unless expicitly stated otherwise. The steps of any method disclosed herein do not have to be performed in the exact order disclosed, unless explicitly stated.

Brief Description of the Drawings

These and other features of the present invention will become apparent from the following description of the exemplary embodiments of the present invention with reference to the drawings, wherein:

Fig.1 is a flowchart performed at a source node according to one exemplary embodiment of the present invention;

Fig.2 shows a simplest circumstance in which a source discovers a mobile sink directly in the flooding process according to one exemplary embodiment of the present invention;

Fig.3 is a flowchart performed at an intermediate node according to one exemplary embodiment of the present invention;

Fig.4 and 7 shows a flowchart according to one preferred exemplary embodiment of the present invention;

Fig. 5 shows a network environment and the moving trajectory of a mobile sink according to one exemplary embodiment of the present invention;

Fig.6 is a flowchart performed at a mobile sink according to one exemplary embodiment of the present invention;

Fig. 8 illustrates the route rediscovery mechanism according to one preferred exemplary embodiment of the present invention;

Figs. 9 and 10 illustrate an exemplary algorithm for determining whether to perform the reroute procedure from the energy point of view according to one preferred exemplary embodiment of the present invention;

Figs. 11 and 12 show how to avoid the transmissions of duplicate messages according to one preferred exemplary embodiment of the present invention;

Figs. 13a-c illustrate simplified function block diagram of apparatus capable of embodied in a source, an intermediate node and a mobile sink respectively according to one exemplary embodiment of the present invention.

Detailed Description of the Invention

A wireless sensor network consists of a number of static sensor nodes and one or multiple mobile sinks, wherein each sensor node has a fixed level of transmission power and has the same transmission range. A packet will be received successfully if the received signal power is greater than the receiving power threshold. Nodes (including both sinks and sensor nodes) have limited transmission range and multihop paths are in general needed for data dissemination among nodes, such as from sensors to the sink. In the following part, a routing solution will be described in detail in reference to the figures. With such routing solution, a path, preferably an efficient path will be found between a sensor node and a mobile sink on which a data processing apparatus is embodied. Therefore, a lightweight streaming data dissemination scheme for wireless sensor networks with mobile sinks is achieved.

The mobile sinks being studied here refers to all existing mobile objects, so long as they can be equipped/enhanced with wireless communication interfaces to communicate with ambient wireless sensor networks, such as mobile handsets, PDA, portable PC, cellular handset, internet tablet, user mobile terminal, laptops, vehicles or the like. Thus, a mobile sink can move randomly and unpredictably. Since the mobile sink operates on a rechargeable battery and has much higher computation and communication capabilities than sensor nodes, it is reasonable that we assume the mobile sink sends out a message/frame announcing the presence of a mobile sink periodically as it moves. In fact, the existing mobile objects are already required to do so in some environments. For example, in IEEE 802.11 networks, beacon frames are used to announce the presence of a Wi-Fi network (as a result, an 802.11 client receives the beacons sent from all nearby APs, even when it is not connected to any network). Other examples are HELLO message, beacon or heartbeat message. We refer to the message periodically sent from a mobile sink to announce its presence as the Hello message hereafter.

In the invention, when a sensor has a bunch of data packets to send, if there is no recent route toward a sink in its routing table, the source node can utilize the routing method illustrated in Fig. 1 to find at least one mobile sink.

Referring to Fig.1 , When a sensor node has streaming data to send (refer to as the source node), e.g., it detects a physical event of interest or the buffered data exceeds a certain amount, and if it finds there is no recent route to a sink in its routing table, at step 101 , it will flood a message (sometimes we call it RouteDiscovery message hereinafter) within K hops to search any available sink nearby. Here, to save transmission overhead, shorten the reply latency, and get enough information if multiple mobile sinks are available, a localized flooding (controlled within K hops) is adopted. Considering specific network environment, K can be a predefined constant or a variant. For reducing the transmission overhead of this process, normally K should be a small value compared with the network diameter. In practical architecture, selection of an appropriate K value depends on the particular environment, such as density and mobility characteristics of the mobile data collectors, thus different regions may have difference K values. If it is found not suitable anymore, such as a source node fails to receive responses (or enough responses) in step 102 (which will be explained below), K value can be increased without exceeding its upper bound (if any).

At step 102, the source node receives one or more replies. We can call such reply as RouteReply. In this stage, not only the mobile sink, but also an intermediate node knows an existing recent route to/toward a mobile sink can return a RouteReply. In this way, the source node can find one or more mobile sinks. If more than one mobile sinks are found, the source node can select a preferred one. Certainly, the source node can also select more than one sinks. For example, if an application has the reliability or delivery latency constraint, the source sensor may send data to multiple sinks along multiple paths in a parallel manner to improve the reliability or delivery latency. Such selection can be made upon taking into account at least one of the following factors: cost of energy; the distance between the source and the discovered mobile sink; cost of time; the processing and forwarding ability/speed of the mobile sink; the security and/or confidence degree of the mobile sink; other application-specific preferences, or the like. In fact, this is an ideal and also the simplest case, i.e., there is at least one mobile sink located within K hops range of the source node. This situation is also shown in Fig. 2, wherein the control message sent by source sensor node is named as RouteDiscovery message. In this case, after receiving RouteReply sent by the mobile sink, the source sensor node can send data to it.

However, if there is no mobile sink within K hops, in other words, If there is no reply come from a mobile sink, the method will go to step 103. At 103, the source sensor node transmits a request (this request is named as SinkRequest in the following description) to at least one intermediate node to find a mobile sink. In this regard, the source sensor node exploits the nearby existing recent route information (i.e., routing information maintained by the selected intermediate node) to discover a mobile sink. Then an end-to-end route from the source to a mobile sink can be built.

The criterions for making a selection, including selecting a preferred intermediate node by the source sensor node, and selecting a preferred mobile sink by an intermediate node, are similar with the selection of mobile sinks by the source sensor node. Such as the most recent and nearest intermediate node is selected.

Now, we will discuss more about how the intermediate node who receives the SinkReply message find a mobile sink with its routing information with reference to Figs 3-4.

Fig. 3 shows the flowchart implemented on an intermediate node according to an exemplary embodiment of the invention. At step 301 , an intermediate node receives a message from a source sensor node. Here the message may be the aforementioned RouteDiscovery. At step 302, if this intermediate node knows some existing recent route to a mobile sink according to its routing table, in other words, if it maintains routing information regarding to a mobile sink, it transmit a reply back to the source sensor node. Here the reply may be the aforementioned RouteReply. At step 303, if a message (such as the aforementioned SinkRequest) sent from the source sensor node is received (in the case that there is no sink nearby and the source node selects one existing recent route to an intermediate node who returns a RouteReply message back, and sends a SinkRequest message, in order to reach the mobile sink), the intermediate node (who replies a RouteReply to the source) utilizes the routing information it maintained to address at least one mobile sink. Upon the discovered mobile sink, an end-to-end path can be built.

Fig. 4 shows how the mobile sink is discovered by an intermediate node in detail. As shown in Fig. 4, when an intermediate node with the knowledge of an existing recent route to a mobile sink receives the SinkRequest message, it forwards this message along its pre-known existing route to the mobile sink. Here we call the sensor node nearest to the mobile sink along this existing route as the access node. When the SinkRequest arrives at the access node, there are two cases: 1 ) the mobile sink is still in its radio range; 2) Due to the random mobility of a sink, it may move out of the access node's radio range. Note this is possible because that the existing route is not so fresh. In case 2, the SinkRequest will be forwarded along the mobile sink's moving trajectory until reaching that mobile sink, which we call chasing mode (in which the SinkRequest message chases the mobile sink along its moving trajectory). Then when the mobile sink receives such SinkRequest message, it makes a decision whether to initiate a route rediscovery process (which will be explained with reference to Fig. 6 later) to rebuild a path. In this example, it does not perform this process. Thus, it replies a SinkReply message to the source node. Upon the received SinkReply message, the source sensor node can send data to the mobile sink along the discovered end-to-end path.

In should be noted that for a person skilled in the art, the moving trajectory can be obtained easily and the specific method for getting such information depending on the particular network environment. For example, obtain such information from other nodes along the moving trajectory, or from a central device serving as a server or the like.

In the chasing mode, the SinkRequest message will be cooperatively forwarded by qualified neighbours toward the moving direction of the mobile sink. The qualified neighbours are defined as the nodes that have fresher HELLO message timestamp than the current forwarding node's (the last hop node) or at least the same HELLO message timestamp with the current forwarding node (depends on the HELLO message broadcasting cycle). It is a contention-based forwarding process, that is, each qualified neighbour who correctly receives this SinkRequest will start timer to contend to be the next-hop forwarder. The timer's value depends on the selected criteria. For example, the selected criteria is that the fresher the HELLO message timestamp is, the higher priority it should be assigned to take the forwarding task, hence the shorter the timer will be. The neighbor whose timer first expires wins the competition to be the downstream next-hop node. Then when the timer expires, the neighbor will broadcast the received SinkRequest until a mobile sink is addressed to, do like the current-hop node. The timer value can be calculated according to different metrics. One common contention policy is that the fresher the HELLO message timestamp is; the higher priority it should be assigned to take the forwarding task, hence the shorter the timer will be.

Although the invention has described the details about the operations of an intermediate node for addressing the mobile sink, a person skilled in the art understand that such issue is not new in the art, and there are other solutions instead.

Fig. 5 gives a more intuitionistic view of the aforementioned Route Discovery and Chasing process. As shown in Fig.5, the source node S has data to send, it first checks whether there is a recent route to a sink. If not, it will flood a RouteDiscovery to search any available sink nearby within K hops. There is no available sink within K hops. However, an intermediate node A knows an existing recent route to a mobile sink according to its routing table; thus, A replies a RouteReply to S. Then S unicasts a SinkRequest to A, and node A forwards this SinkRequest along the existing route to reach that sink. Because the route to a mobile sink is recent but not freshly discovered, when this SinkRequest arrives at node B (access node), the mobile sink has moved out of B's radio range. In this case, the SinkRequest is forwarded along the mobile sink's moving trajectory until reaching the sink. When the mobile sink receives the SinkRequest, according to its own judgment, it may return a SinkReply message along the reverse path to the source node, or it initiate a Route Rediscovery procedure, which will be described in the subsequent portion of this description.

Now we discuss about the aforementioned rediscovery made by a discovered mobile sink. It should be noted that this rediscovery process is a preferred embodiment of the invention, this means in some embodiments, such rediscovery process is not a necessary portion of the invention. This Route Rediscovery procedure allows a longer distance routing path connecting the source node to a mobile sink to be redirected to a shorter distance routing path in an energy efficient manner.

The Route Rediscovery is composed of two phases: 1 ) flooding a message (such as a RouteRediscovery message shown in Fig. 7) from the mobile sink within limited hops (the hop-count of this flooding operation is denoted as L); 2) the nodes who have a route to the source will forward the flooded message to the source (such as the nodes who have received the RouteDiscovery message in the previous Route Discovery phase will transmit, preferably unicast this RouteRediscovery along their reverse pathes to the source node).

Fig. 6 shows the route rediscovery process implemented by a mobile sink. At step 601 , a discovered mobile sink can make a decision to determine whether to rebuild a path to a source. If it determines to rebuilt a path, at step 602, it floods a message (such as RouteRediscovery message shown in Fig. 7) within limited hops of a network. In route rediscovery process, the nodes who maintain related routing information to the source will transmit the received RouteRediscovery message to the source. Such nodes can be the nodes who have received the RouteDiscovery message in the previous (in other words, nodes locate within the flooding range of the source sensor node), those nodes will unicast the flooded message to the source.

In a preferred embodiment, a mobile sink will determine to rebuild a path to a source, if it founds the probability of rebuilding a path, preferably a path shorter than the current path connecting the source to this mobile sink is very high, or its estimated probability is higher than a required value/threshold. Specifically, a mobile sink can estimate the probability of rebuilding such (shorter) path by its experiences and/or its maintained routing information. For example, if the flooding hop-count is no less than the difference of hop-count of the current path and the flooding hop-count of the source (which will be explained with reference to Figs. 9 and 10 later), or if there is an apparatus locate within the limited flooding range of the source and the data processing apparatus (in other words, there is an overlapping region of the flooding by the source and the mobile sink), at least a path can be built. Or the probability can be estimated on the trajectory of the current path, or analysis of angles of segments of the current path (preferably with location information).

In a preferred embodiment in which analysis of angles are used, some location information may be necessary obtained for example, by using directional antennas or other existing methods. Another example is that, in heterogeneous wireless sensor networks where the source node may have stronger capability (i.e., knows its location) than other neighboring nodes, the source will take charge of the local data collection and aggregation/fusion and send the aggregated data to a mobile sink. That is to say, the source node, access node and the mobile sink know their locations. It should be noted that although some of the embodiments of the invention release the necessity of utilizing location information, the invention doesn't exclude such utilization of location information. This is because some location information may facilitate a mobile sink to get angles between segments of a path. Specifically, if we divides the current path into several segments, such as the path connecting the source node and the intermediate node (denoted as HCi in Figs.7, 9, 10), the path connecting the access node (if any) and the mobile sink (denoted as HC₃ in Figs.7, 9, 10), and the path connecting the intermediate node and the mobile sink (denoted as HC₂ in Fig. 9), we can consider the angles between those segments (with obtained location information), and the smaller those angles are, the more curve the current path is. If we go to Figs. 9 and 10, we can see that the smaller the angles between the shown segments, the higher possibility for a mobile sink to find a shorter path. Then a mobile sink can make a determination on the basis of the value of those angles. In addition, the angles can be compared with certain predefined thresholds. Thus one or more parameters can be set appropriately depending on such as the routing experience and the specific application circumstances. Then if the angles are smaller than the parameters, a route rediscovery process can be initiated. Simply speaking, such estimations (maybe a rough one) of angles can be made based on the moving trajectory of a mobile sink, or an intuitionistic estimation can be made based on the graphic of the current routing path from the source, such as the one as shown in Fig. 5.

In another preferred embodiment, a mobile sink can make the determination based on the energy cost analysis. Preferably, a mobile sink can simply make the determination on the comparison of an estimation of the energy cost with a threshold (which can be set predefined or can be adjust timely to accommodate the current network circumstances). In this case, if the energy cost is acceptable, a route rediscovery will be initiated. Alternatively, the mobile sink can compare the energy cost for building a shorter path and the energy saving brought our by the shorter path, and only if energy saving dominates (the cost of energy for building a shorter path is less than the saving energy brought out by the rebuild path) the route rediscovery operation will be initiated. In a preferred embodiment, the energy cost for building a shorter path can comprise the cost of the above flooding operation and the cost of the aforementioned preferred unicasting operation. When estimating the energy cost and energy saving, one or more of the following factors can be taken into account: the number of nodes within the flooding rage (or node density, flooding area), the number of paths that the message will be transmitted to the source, the hop-count from the intermediate apparatus to the source, the amount of data to be transmitted from the source to the data processing apparatus, the expected reduced hop-count by the shorter path comparing with the current path. Wherein the above information can be maintained by a mobile sink, or it can be derived/estimated from the mobile sink's maintained routing information with experiences.

In addition, a person skilled in the art can easily conceive many other factors to be considered in making such decision. For example, the determination can be made based on the application-specific requirements and characteristics, or the specific network circumstances or the like.

In addition, another advantage is that after the Route Rediscovery, if a mobile sink knows location information, a rough estimation on the location of the source can be made by the mobile sink. For example, after Route Rediscovery, a mobile sink in chasing mode can make such estimation based on HC3, HC4 and HC5 as shown in Fig. 10 with its current location and previous location. Simply speaking, a combination of the length of some segments of the current path and the rebuild path together with certain location information, it is possible for the mobile sink to make said estimation. Then the mobile sink can report its estimated location information to others. Preferably, the estimated location information is sent together with the sensor data to an intended destination, such as a remote data center through some other access method, e.g, through 3G to access the Internet.

Also, if a mobile sink knows its location information, it can rebuild a path to the source through geographic greedy forwarding based on location information. Specifically, the mobile sink knows the source's location and all nodes are location-aware, then as the location are available, there is no need to using hop count to estimate the distance. In geographic routing, nodes need to know only the location information of their direct neighbors and where the destination is. A person skilled in the art knows that the basic idea for geographic routing is greedily forwarding data packets to the neighbor geographically closest to the destination. For each hop in greedy forwarding, the neighbor closest to the destination will be selected as the next-hop node. Thus in this invention, when the mobile sink receives the SinkRequest message from the source, if it knows the soure's location, the mobile sink will send a RouteRediscovery message to notify the source through geographic greedy forwarding.

Fig. 7 shows a flowchart of another embodiment in which the discovered mobile sink decides to perform the route rediscovery process. In Fig. 7, the mobile floods a RouteRediscovery message within L (as illustrated with reference to Figs. 9 and 10, L is no less than HC1 +HC2+HC3-K), which can guarantee that the RouteRediscovery can find a path to the source node. The node within the flooding range of the source node has a route to the source (this route can be learned when the source node sends out the RouteDiscovery message) will send the RouteRediscovery message along the RouteDiscovery's reverse path to the source node.

An example of the Route Rediscover mechanism is given in Fig. 8. Here, the flooding of RouteRediscovery is limited in a certain range. The nodes who have received the RouteDiscovery message in the previous Route Discovery phase will unicast this RouteRediscovery along their reverse paths to the source node. Then the source node may receive multiple RouteRediscovery messages, and it will select a preferred path, e.g., the path with least hop count.

The objective of the Route Rediscovery is trying to find a shorter path to the source and therefore save energy consumption for the subsequent data dissemination. This is important for not only mobile sinks but also static sinks. For a mobile sink, the new shorter path can save energy. For a static sink, maybe initiate this process will not save much energy for the current data dissemination, or maybe the energy cost dominates, but this process is still useful for the following/subsequent data transmission.

However, as this process also introduces overhead, i.e., the flooding of RouteRediscovery message from the mobile sink, If not addressed carefully, this overhead may exceed the savings brought by the Route Rediscovery mechanism. Thus it is preferred to consider the precondition for adopting such Route Rediscovery mechanism for saving energy. This concern seems varies from condition to condition, and the answer will be different for different applications, different specific environments, or even varies with time under the same network deployment. Anyway, the decision of whether to initiate such rediscovery procedure depends on specific requirements.

As aforementioned, when we make the decision from the aspect of energy saving for a mobile sink, we can estimate the energy cost roughly. In addition, we can also make a relatively exact estimation. Below we will illustrate an exemplary algorithm, in which the cost of energy for rebuilding a path to a source can be calculated and compared with the saving energy brought out by the rebuild path. If the cost energy is less than the saving energy, i.e., the energy saving dominates, flooding a RouteRediscovery message within L hops will be performed.

Therefore, as an illustrating embodiment of the invention in which energy is considered for determining whether to initiate the route rediscovery process, inventors design an algorithm to ensure that energy saving dominate. Referring to Figs. 9-10, The details of the algorithm design are presented in following.

In this embodiment, a current path connecting a source to a discovered mobile sink is divided into several segments. As shown in Fig. 9, we let HC1 denote the hop-count connecting the source node to the selected intermediate node, e.g., the route SA in Fig. 5. HC2 denotes the hop-count connecting the selected intermediate node to the access node, e.g., the route AB in Fig. 5. HC3 denotes the hop-count connecting the access node to the mobile sink, e.g., the route BC in Fig. 5. When the SinkRequest reaches the mobile sink, the mobile sink knows HC1 , HC2 and HC3 (if any). Let HC5 denote the hop-count of the new discovered route between the source node and the mobile sink when adopting the Route Rediscovery scheme. We normalize one hop as one unit of length.

The intuition of this algorithm in this embodiment is that a mobile sink should send a RouteRediscovery if the Route Rediscovery can introduce more savings than costs. To find when the mobile sink should send a RouteRediscovery message, the algorithm takes a relatively exact cost analysis approach.

In the following derivations, we assume the sensor nodes are evenly distributed, i.e., the number of nodes receiving a broadcast packet is roughly equal. The cost of a transmission consists of the sending cost of the sender, and the receiving cost of a fixed number of receivers. Hence, the transmission cost is proportional to the sending cost. We define the cost of a Data transmission as one cost unit. Assuming that the packet size ratio between a control message (RouteRediscovery, etc.) and a Data packet is ^ , therefore, the transmission cost of a RouteRediscovery is^ . We define the node density NodeDensity as the average number of nodes deployed per unit area. That is to say, given the size of an area, we can estimate the number of sensor nodes in this area.

When a SinkRequest arrives at the access node, there are two cases: 1 ) the mobile sink is still in its radio range; 2) it may move out the access node's radio range. In the following, we discuss for different cases.

Firstly, we consider case (1 ), the mobile sink is still in the access node's radio range. As shown in Fig. 9, when a SinkRequest arrives at the access node B, the mobile sink is still in B's radio range.

We now derive the energy cost when adopting the Route Rediscovery mechanism. Given HC1 and HC2, we know | HC1 -HC2 | and | HC1 +HC2 | are the lower bound and upper bound of HC5, respectively. Since the source node has flooded a RouteDiscovery message within K hops, i.e., all nodes in the RouteDiscovery flooding area will receive this message, as shown in Fig.9. Thus, the hop-count (aforementioned parameter L) of flooding of RouteRediscovery message can be selected as no less than (HC1 +HC2-K), in order to guarantee that the RouteRediscovery can find a path to the source node. Then, in the condition that it guarantees the RouteRediscovery can find a path, the upper bound of the cost (here "upper bound" means the upper bound of the cost for guarantee a path can be found in the RouteRediscovery procedure, if L is set less than (HC1 +HC2-K), energy cost will be reduced, but it maybe failed to find a path to the source in the rediscovery procedure, the vaule of L can be set on basis of the required probability of find a path to the source; if L is set larger than (HC1 +HC2-K), the energy cost will certainly increase, however, the larger value is not necessary for the above "guarantee") introduced by the Route Rediscovery, denoted by£ , is composed of two parts, the RouteRediscovery flooding cost ^π (HCⁱ + HCⁱ - K)² - NodeDesity - λ _{> and} the unicasting cost along a RouteDiscovery reverse path. K \$ the estimated upbound cost of the unicasting along a RouteDiscovery reverse path, and we estimate there are ¹¹ paths along which the RouteRediscovery is unicasted on average. We have,

£ = π^■ (HCi + HCi - Kf ^■ NodeDesity - λ + η - Κ

(1 )

Let be the direction between SA and AB. Given an , according to the cosine formula, HC5 is a deterministic value.

HCs = VHCi² + HCi - 2 · HCi · HCi^■ cos Θ

Considering the randomness of ^ , i.e, ^ satisfies uniform distribution between 0 and ^2;r . Then, we have the expectation of HC5,

Let M denote the number of packets waiting for transmission from the source node. By adopting the Route Rediscovery, the expected saving (HC₁ + HC₂ - E(HCs)^^■ M

ensure that the expectation of the Route

Rediscovery mechanism can save energy, we have

£ < ( HC_X + HC₂ - E(HCs))^■ M

(4)

When the mobile sink receives a SinkRequest, it checks whether Inequality (4) holds. If yes, it will adopt the Route Rediscovery mechanism. If a new route is built, the source will send Data packets to the mobile sink along the new route.

Next, we proceed to describe the case when the mobile sink receives a SinkRequest in chasing mode, i.e., the mobile sink moves out the access node's radio range, as shown in Fig. 10. Fig. 10 shows when a SinkRequest arrives at the access node B, due to the random mobility of a sink, it moves out the access node's radio range. Thus, SinkRequest will be forwarded along the mobile sink's moving trajectory until reaching the mobile sink, which we call the packet chasing mode.

Given HC1 , HC2 and HC3, we know | HC1 +HC2+HC3 | is the upper bound of HC5. Since the source node has flooded a RouteDiscovery message within K hops, i.e., all nodes in the RouteDiscovery flooding area will receive this message, as shown in Fig.10. Thus, similarly, the flooding range (parameter L) of RouteRediscovery message needs to be set no less than (HC1 +HC2+HC3-K), to guarantee that the RouteRediscovery can find a path to the source node. The upper bound of the cost introduced by the Route Rediscovery, denoted by£ , is:

£ = π^■ (HCi + HCi + HCs - K)^2■ NodeDesity - λ + η - Κ ^

Let be the direction between SA and AB; ² be the direction between

SB and BC. Let ^HC4 denote the expected hop-count connecting the source node to the access node. We have

Similarly, we have the expected hop-count of the new discovered route between the source node and the mobile sink when adopting the Route Rediscovery mechanism.

To ensure that the expectation of the Route Rediscovery can save energy, we have

£ < (HCi + HC2 + HC3 - E(HCs)) M

(8)

If the mobile sink receives a SinkRequest, it checks whether Inequality (8) holds. If yes, it will adopt the Route Rediscovery mechanism. If a new route is built, the source will send Data packets to the mobile sink along the new route.

In the Route Rediscovery, in order to guarantee that the RouteRediscovery can find a path to the source node, the protocol can define a system parameter, which is the maximum hop count it will flood the RouteRediscovery message. Its value can be smaller than (HC1 +HC2-K) or (HC1 +HC2+HC3-K). As aforementioned, this depends on the required probability of finding a path in a RouteRediscovery procedure.

Note that another benefit from the Route Rediscovery mechanism is that all nodes having received the RouteRediscovery message, such as nodes within the RouteRediscovery flooding area, can take this opportunity to update their related routing information (such as routing tables) toward that mobile sink, i.e., recording that it has recently witnessed a mobile sink nearby.

For the above algorithm, simply speaking in words instead of formulation, the cost of flooding the RouteRediscovery message from the mobile sink can be calculated based on estimation of the node density (which is defined as the average number of nodes deployed per unit area based on either the pre-configuration or local neighborhood knowledge, e..g., by calculating the number of one-hop neighbors), the flooding area (it is assumed as a circle here, but certainly other shapes are also applicable, such as a fan-shaped region towards the source), then obtains the number of nodes within the flooding range. The cost of unicasting the RouteRediscovery message can be obtained based on estimation of the number of paths that the RouteRediscovery will be unicasted to the source node, and K hop of the upper bound of the unicasting along the RouteDiscovery reverse path (then the transmission cost of unicasting the RouteRediscovery message can be obtained). Wherein the energy saving when a shorter distance routing path is found can be calculated based on, the number of the packets to be transmitted to the selected mobile sink, the estimated deduced hopcout by adopting the Route Rediscovery mechanism (the difference between the total hop-count of the longer distance routing path connecting the source node to a mobile sink and the expected hop-count of the shorter distance routing path Calculating), then the reduced transmission cost (the energy saving) brought the Route Rediscovery mechanism can be calculated.

Considering the limitation of mobile sink on processing power and memory space, it is not easy to calculate the expected hop-count. To reduce the computation complexity, Newton-Cotes formula, a method of numerical integration, can be applied to calculate the approximate value of expected hop-count.

For example, to calculate HC₅ in case 1 , the Newton-Cotes formula degree n is set 3, define F(0) as follow:

/(0) = VHCi² + HCi - 2 · HCi · HCi^■ cos Θ

We have

1 2π 4π

E{HCs) * -{/(0) + 3/(— ) + 3/(— ) + (2π) }

J J

=— I HCi - HCi I +-VHC1² + HCi + HCi H 2

4 4

Then, we can get the critical value of HC2, i.e., at the time to determine whether to send the RouteRediscovery for a mobile sink.

Another consideration for improving the invention is reducing unnecessary transmission. For an identical control message, which is uniquely identified by the source node id and a sequence number, any node will take the forwarding task once at most. Besides, we use overhearing and cooperative forwarding to reduce unnecessary transmissions. The principle of overhearing is that because the wireless medium is shared, each node can overhear packets sent by its neighbours. Then if a node founds the same packet has been forwarded by its neighbour, it drops such packet.

Now we give specific examples to illustrate the optimization mechanisms for performance improvement. Fig. 11 shows an example illustrating such optimization mechanisms. In Fig. 11 , a source node S sends a RouteDiscovery. Nodes A, B, C, D and E know an existing route to the same mobile sink. A first replies a RouteReply to S, which includes the sink id and the hop-count to that mobile sink. Nodes C, B, D overhear this RouteReply. Since A has replied the RouteReply, they know that their replies are redundant. However, Node E does not know A has replied the RouteReply, it sends a RouteReply to B. Then upon overhearing, B will drop this RouteReply.

Fig. 12 shows another example of forwarding the SinkRequest in chasing mode, in which newly broadcasted SinkRequest will also suppress other neighbours' contention, i.e., other neighbours who overhear this SinkRequest will cancel their contention timer. Specifically, node A forwards a SinkRequest along the sink moving trajectory. Nodes B, C, D are qualified to forward the SinkRequest (i.e., they have the same timestamps and are no less than As timestamp). They contend to serve as the next forwarder. D wins the contention and forwards the SinkRequest to its downstream neighbours. But B is out of the radio range of D, thus B will also forward the SinkRequest to its downstream neighbours, e.g., node E. In this case, the packet duplication problem would occur. However, E witnesses that F has forwarded the SinkRequest to G. Thus, when E receives the SinkRequest from B, it will drop this message.

The above content has explained the operations performed on a source sensor node, an intermediate node and a mobile sink. A person skilled in the art can readily understand that the new operations of the invention can be implemented as software, hardware, firmware, or the combination thereof. Therefore, any apparatus with at least the ability of implementing the invention can be deployed on the existing nodes in networks, in order for implementing the invention. In addition, it should be noted that the proposed apparatus can be a separate entity, or embodied into other existing device, apparatus, or functional blocks.

Figs. 13a-13c shows exemplary embodiments of the implementations of apparatus operating on the source sensor node, an intermediate node and a mobile sink respectively. As shown in those figures, the apparatus have respective means for performing each step of respective methods. For example, the apparatus in 13a to be deployed in an existing source sensor node has a flooding means, receiving means and transmitting means. Alternatively, the structure of this apparatus can be changed as comprising a transceiver/wireless interface and a control unit/means. In this case, the transceiver/wireless interface will be responsible for communicating, including sending and receiving, while the control unit will perform other operations, such as deciding to perform the flooding operation and instructing the interface to perform the specific flooding.

The apparatus shown in Fig. 13b can be embodied in an intermediate node. Similarly, it has receiving means, transmitting means and addressing means for implementing corresponding method. In addition, it may have a cash area, such as a memory, a disk or the like to maintain its routing information. Certainly, instead of storing in the apparatus of the invention, such routing information can be stored in the intermediate node itself or some peripheral equipment. Also, such apparatus can be realized in other structure, such as a hardware interface, and a central processing unit or a processor for performing other functions of this apparatus.

The apparatus shown in Fig. 13c can be embodied in a mobile sink. It has decision making means and flooding means, and similarly, it can also embodied as other forms, such as hardware, the combination of hardware and software, etc. In a preferred embodiment in which energy cost is considered when making a decision, the apparatus may further comprise a calculating means for implementing the specific calculating function.

Of course, the above functions of respective apparatus will not exclude other functions being embodied in the apparatus. Thus the apparatus may have other works to fulfill.

Although the foregoing content uses a wireless sensor network, a sensor node, a mobile sink in preferred embodiments of the invention, the invention should not be limited thereto. In fact, the invention is also applicable for a network in which a plurality of data packet often needs to be transmitted. In addition, it is obvious that the sink can also be static. In this case, the chasing process and the route rediscovery are not necessary. Then for sink of the invention, it can be any kind of data processing apparatus with necessary interface for communications of the network, and it also has certain ability of processing data, such as gathering/receiving/transmitting data from the source.

Once an end-to-end route is constructed with the invention, the data transmission is comparatively simple. A bunch of data packets will be forwarded along the discovered route to the mobile sink. Since the end-to-end route is fresh enough (the mobile sink replies the SinkReply to the source or the mobile sink initiates a Route Rediscovery procedure immediately), during the data packets being forwarded toward the mobile sink, considering the limited moving speed of mobile sinks (e.g., for mobile users, the walking speed is among 1 -2m/s, while the sensor node radio range is 50m on average), that mobile sink won't move far away from the new access node. Even if the mobile sink has moved out of the access node's radio range, the data packets can be delivered to the mobile sink following the sink moving trajectory within limited hops. This process is similar as the chasing mode, it is expected that the data packet can chase the mobile sink within limited hops, e.g., one or two hops, because the end-to-end route is fresh. Therefore, with the routing scheme of the invention, a lightweight streaming data dissemination scheme for wireless sensor networks with mobile sinks is achieved.

Considering in many practical situations, it is heavily power-consumed and costly to equip expensive GPS devices in the cheap sensor nodes, and the location information calculated by a localization algorithm or the GPS may be not accurate, thus compared with prior art, the invention release the necessity of utilizing any location information.

With the utilization of a localized limited flooding and even the nearby existing recent route information, the invention establishes the route to a mobile sink. In this invention, it is scalable because the flooding scale will not increase as the network size increases. Compared with the hierarchical flooding approach, it avoids the construction of the hierarchical structures. In addition, localized flooding enables the source node to select the least cost route to send data and introduces shorter reply latency. Therefore, the routing scheme presented in this invention achieves timely delivery of collected data.

In should be noted that the described features, advantages, and characteristics of the invention may be combined in any suitable manner in one or more embodiments. One skilled in the art will recognize that the invention may be practiced without one or more of the specific features or advantages of a particular embodiment. In other instances, additional features and advantages may be recognized in certain embodiments that may not be present in all embodiments of the invention. Also, those means, modules and/or steps may be implemented as a separate one or can be combined with any others or it can be split into several means, modules, steps according to their functionality.

The present invention can be realized in hardware, software, firmware or a combination thereof. It is applicable for the present invention to be implemented as a computer program product, which comprises all the features enabling the implementation of the methods and devices or modules described herein, and when being loaded into a computer system or a processing device, is able to carry out these methods or constitute the functional means/modules in the apparatuses or devices according to embodiments of the present invention. In addition, said program products can be embodied in computer readable medium. For example, a program of the computer program product can be loaded into/embodied in a memory of the processing device.

Although the above description has discussed specific embodiments of the invention, those skilled in the art can understand that changes can be made to the specific embodiments without departing from the spirit and scope of the invention. The scope of the invention is not to be restricted therefore to the specific embodiments, and it is intended that the appended claims cover any and all such applications, modifications, combinations and embodiments within the scope of the present invention.

Claims

1 . A method, comprising:

flooding a message within limited hops to discover at least one data processing apparatus of a network;

in response to said flooding, receiving at least one reply;

if there is no reply coming from a data processing apparatus, transmitting at least one request to an intermediate apparatus from which the reply is sent, to discover at least one data processing apparatus with the routing information maintained by the intermediate apparatus.

2. The method according to claim 1 , further comprising:

3. The method according to claim 2, wherein said selecting can be made on the basis of at least one of the following: distance, the cost of energy, the cost of time, security, confidence, the processing and forwarding ability/speed, application-specific preferences/characteristics, whether the maintained routing information is recent.

4. The method according to any one of claims 1 to 3, wherein an end-to-end path can be built to the discovered data processing apparatus, then data can be transmitted to the discovered or selected preferred data processing apparatus.

5. The method according to any one of claims 1 -4, wherein the request is further forwarded by the intermediate apparatus to a data processing apparatus on the basis of its routing information or the combination of its routing information and the moving trajectory of the data processing apparatus.

6. The method according to any one of claims 1 -5, wherein the network is a wireless network or a wireless sensor network, and the data processing apparatus is a mobile sink or a static sink.

7. The method according to claim 6, if the data processing apparatus is a mobile sink, the mobile sink is discovered by the intermediate apparatus based on routing information or routing information in combination with moving trajectory of the mobile sink maintained by the intermediate apparatus; if the data processing apparatus is a static sink, the mobile sink is discovered based on routing information maintained by the intermediate apparatus directly.

8. The method according to any one of claims 1 -7, wherein upon overhearing, duplicate transmissions of replies and/or requests can be avoided; and/or a discovered data processing apparatus can rebuild a path to a source through geographic greedy forwarding based on location information.

9. An apparatus, comprising

at least one processor; and

at least one memory including computer program code;

the at least one memory and the computer program code are configured to, with the at least one processor, cause the apparatus to perform at least the following:

in response to said flooding, receive at least one reply;

if there is no reply coming from a data processing apparatus, transmit at least one request to an intermediate apparatus from which the reply is sent, to discover at least one data processing apparatus with the routing information maintained by the intermediate apparatus.

10. The apparatus according to claim 9, further perform:

if more than one data processing apparatuses are discovered, select at least one preferred data processing apparatus; and/or

if a plurality of replies have been received from more than one intermediate apparatuses, select at least one preferred intermediate apparatus to transmit said request.

11 . The apparatus according to claim 10, wherein selection can be made on the basis of at least one of the following: distance, the cost of energy, the cost of time, security, confidence, the processing and forwarding ability/speed, application-specific preferences/characteristics, whether the maintained routing information is recent.

12. The apparatus according to any one of claims 9 or 11 , wherein an end-to-end path can be built to the discovered data processing apparatus, then data can be transmitted to the discovered or selected preferred data processing apparatus.

13. The apparatus according to any one of claims 9-12, the request is further forwarded by the intermediate apparatus to a data processing apparatus on the basis of its routing information or the combination of its routing information and the moving trajectory of the data processing apparatus.

14. The apparatus according to any one of claims 9-13, wherein the network is a wireless network or a wireless sensor network, and the data processing apparatus is a mobile sink or a static sink.

15. The apparatus according to claim 14, if the data processing apparatus is a mobile sink, the mobile sink is discovered by the intermediate apparatus based on routing information or routing information in combination with moving trajectory of the mobile sink maintained by the intermediate apparatus; if the data processing apparatus is a static sink, the mobile sink is discovered based on routing information maintained by the intermediate apparatus directly.

1 6. The apparatus according to any one of claims 9-15, wherein upon overhearing, duplicate transmissions of replies and/or requests can be avoided; and/or a discovered data processing apparatus can rebuild a path to the apparatus through geographic greedy forwarding based on location information.

17. A method, comprising:

receiving a message for discovering a data processing apparatus flooded within limited hops of a network;

18. The method according to claim 17, wherein a path from a source sending the message to the discovered data processing apparatus can be built, and data can be transmitted to the data processing apparatus.

19. The method according to claim 17 or 18, wherein the network is a wireless network or a wireless sensor network, and the data processing apparatus is a mobile sink or a static sink; and/or the addressing comprising forwarding the feedback request from the intermediate apparatus to a data processing apparatus; and/or if the data processing apparatus is a mobile sink, it is discovered based on maintained routing information or routing information in combination with its moving trajectory; and/or if the data processing apparatus is a static sink, it is discovered based on maintained routing information directly.

20. The method according to any one of claims 17-19, wherein if a message sent by the discovered data processing apparatus for rebuilding a path to a source is received, unicasting the received message to the source from which message for discovering a data processing apparatus is flooded; and/or upon overhearing, duplicate transmission of replies and/or feedback requests can be avoided.

21 . A apparatus, comprising

at least one processor; and at least one memory including computer program code;

22. The apparatus according to claim 21 , wherein a path from a source sending the message to the discovered data processing apparatus can be built, and data can be transmitted to the data processing apparatus.

23. The apparatus according to claim 21 or 22, wherein the network is a wireless network or a wireless sensor network, and the data processing apparatus is a mobile sink or a static sink; and/or the addressing comprising forwarding the feedback request from the intermediate apparatus to a data processing apparatus; and/or if the data processing apparatus is a mobile sink, it is discovered based on maintained routing information or routing information in combination with its moving trajectory; and/or if the data processing apparatus is a static sink, it is discovered based on maintained routing information directly.

24. The apparatus according to any one of claims 21 -23, wherein if a message sent by the discovered data processing apparatus for rebuilding a path to a source is received, unicast the received message to the source from which message for discovering a data processing apparatus is flooded; and/or upon overhearing, duplicate transmission of replies and/or feedback requests can be avoided.

25. A method, comprising determining whether to rebuild a path to a source;

wherein the message will be further transmitted to the source by an intermediate apparatus with its maintained routing information.

26. The method according to claim 25, wherein the intermediate apparatus locates within a limited flooding range of the source in which a message for discovering a data processing apparatus has been flooded; and/or the determination can be made based on the required probability of rebuilding a path or rebuilding a path shorter than the current path connecting the source to the data processing apparatus, and/or an energy cost analysis.

27. A method according to claim 26, wherein a path can be built if the flooding hop-count is no less than the difference of hop-count of the current path and the flooding hop-count of the source, or if there is an apparatus locate within the limited flooding range of the source and the data processing apparatus; and/or the probability of rebuilding a shorter path can be estimated on the trajectory of the current path, or angles of segments of the current path together with location information; and/or the energy cost analysis comprising the energy cost for building a shorter path and/or the energy saving brought out by the shorter path.

28. A method according to claim 26 or 27, wherein the energy cost and energy saving can be estimated from the one or more of the following factors maintained by a data processing apparatus or derived/estimated from its maintained routing information with experiences: node density, flooding area, the number of nodes within the flooding rage, the number of paths that the message will be transmitted to the source, the hop-count from the intermediate apparatus to the source, the amount of data to be transmitted from the source to the data processing apparatus, the reduced hop-count by the shorter path comparing with the current path; and/or a method of numerical integration can be used to reduce the computation complexity.

29. A method according to any one of claims 25-28, wherein upon overhearing, duplicate transmissions can be avoided; and/or an intermediate apparatus overhearing the flooded message can update its related routing information; and/or the message is transmitted unicastly; and/or the flooding of the data processing apparatus can be approximately a circular or fan-shaped region.

30. An apparatus, comprising

at least one processor; and

at least one memory including computer program code;

determine whether to rebuild a path to a source;

31 . The apparatus according to claim 30, wherein the intermediate apparatus locates within a limited flooding range of the source in which a message for discovering a data processing apparatus has been flooded; and/or the determination can be made based on the required probability of rebuilding a path or a path shorter than the current path connecting the source to the data processing apparatus, and/or an energy cost analysis.

32. The apparatus according to claim 31 , wherein a path can be built if the flooding hop-count is no less than the difference of hop-count of the current path and the flooding hop-count of the source, or if there is an apparatus locate within the limited flooding range of the source and the data processing apparatus; and/or the probability of rebuilding a shorter path can be estimated on the trajectory of the current path, or angles of segments of the current path together with location information; and/or the energy cost analysis comprising the energy cost for building a shorter path and/or the energy saving brought out by the shorter path.

33. The apparatus according to claim 31 or 32, wherein the energy cost and energy saving can be estimated from the one or more of the following factors maintained by a data processing apparatus or derived/estimated from its maintained routing information with experiences: node density, flooding area, the number of nodes within the flooding rage, the number of paths that the message will be transmitted to the source, the hop-count from the intermediate apparatus to the source, the amount of data to be transmitted from the source to the data processing apparatus, the reduced hop-count by the shorter path comparing with the current path; and/or a method of numerical integration can be used to reduce the computation complexity .

34. The apparatus according to any one of claims 30-33, wherein upon overhearing, duplicate transmissions can be avoided; and/or an intermediate apparatus overhearing the flooded message can update its related routing information; and/or the message is transmitted unicastly; and/or the flooding of the data processing apparatus can be approximately a circular or fan-shaped region.

35. An apparatus, comprising respective means for implementing steps of any one of the preceding method claims.

36. A computer program product comprising computer-executable components with instructions for implementing method or apparatus according to any of claims 1 -35.

37. A computer program product according to claim 36, wherein the program is embedded in a computer readable medium.