Abstract:
A soft state framework to support routing functionality in a mobile wireless sensor network is provided. This invention allows each node of the wireless sensor network to move in random directions in a three dimensional space. The invention seeks to minimize resource consumption while optimizing routing functionality in a mobile condition.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates generally to routing protocols. More particularly, the present invention relates to a soft state routing protocol for mobile wireless sensors in a wireless sensor network. 
         [0003]    2. Description of Related Art 
         [0004]    A wireless sensor network (WSN) is a self-organizing wireless network that consists of distributed devices with sensors commonly referred to as “nodes”. The sensors are of application specific. They are used for monitoring environmental conditions, such as sound, temperature, vibration, pressure, motion or pollutants at different locations. The wireless sensor network was originally motivated by military applications. It is now widely used in many industrial, agricultural, medical and other civilian applications. 
         [0005]    In addition to the sensors, each device in a WSN is equipped with elements such as a radio transceiver, microcontroller, flash memory, antenna, energy source and so on. A WSN device is typically low data rate, low cost and low power devices. The low cost of a WSN is a constraint on system resources such as energy, memory, processor and bandwidth. 
         [0006]    IEEE 802.15.4 is a standard which specifies the physical layer and media access control for Wireless Sensor Network. In this standard, there are two types of multi-access mechanisms: beacon and non-beacon. In a beacon enabled network, nodes transmit in specific time slots. The sink node, also referred to as the coordinator periodically sends a beacon frame. All nodes in the WSN are expected to synchronize to this frame. Each node is assigned a specific slot to transmit and receive its data. There is also a common slot during which all nodes compete to use the channel. In a non-beacon enabled network, all nodes in a network can transmit at any time when the channel is available. 
         [0007]    There are usually three types of WSN devices, i.e. the coordinator (or sink), router and end device. The first two devices have routing functionality. Both devices have ability to find proper routes to forward packets to desired destinations. An end device has no routing ability, it only communicates with a specific router that is called the parent of the end device. 
         [0008]    If the routing condition changes so that the original path becomes unavailable, the routers are able to find a new path to deliver the packets to the destination. Currently, the WSN devices are usually installed in fixed locations. However, if the devices were installed inside a moving target, the routing among the wireless nodes becomes a challenge. 
         [0009]    Currently, there are a few routing solutions for partially mobile WSN: 
         [0010]    Mobile base station (MBS) based solutions: A MBS is a mobile sink that changes its position within a WSN. The packets are sent to the MBS via relay node. 
         [0011]    Mobile data collector (MDC) based solutions: A MDC is a mobile sink that visits sensors. The packets are buffered at source nodes until the MDC visits the sensors. The data is sent over to the MDC without relay nodes. 
         [0012]    Rendezvous based solutions: The data is sent to rendezvous nodes that are closer to the mobile sink. The packets are buffered at the rendezvous nodes until the sink receives them. 
         [0013]    However, these solutions are restricted in that all the nodes must be fixed except the sink node. Therefore, the mobility is substantially limited. 
         [0014]    Further some basic soft state refreshment methods exist such as: 
         [0015]    A specific timer that is associated with each individually sent refreshing message. This approach is inefficient and consumes copious resources for refreshing processes. 
         [0016]    In another soft state method, the refreshing messages are flooded to the network altogether once the timer fires. This approach can overwhelm local devices, creating broadcast storms over the network, hence a packet can be lost. On the other hand, the refreshing process is in sleeping mode and does nothing before the timer triggers. This brute force approach eliminates the possibility to customize the refreshment. 
         [0017]    Another soft state method involves bundling a subset of the refreshing messages into a single packet which is sent to the wire when the timer fires. This is a compromise to the previous two methods. Still, this approach cannot provide a resolution to take care of specific requirements. 
         [0018]    The third approach is an improvement to the previous two ways, however, in general the current approaches perform refreshing action with very limited intelligence. 
         [0019]    Therefore, what is needed is a routing protocol that may efficiently allow for all nodes to be mobile. Moreover, a more efficient soft state solution may be desirable to enhance routing functionality in a mobile WSN. 
       SUMMARY OF THE INVENTION 
       [0020]    The subject matter of this application may involve, in some cases, interrelated products, alternative solutions to a particular problem, and/or a plurality of different uses of a single system or article. 
         [0021]    Routing protocols are the critical modules and major resource consumers of the software in a Wireless Sensor Network (WSN). These modules require a significant amount of system resources including electric power. It is a big challenge to provide routing functionality in a WSN because the wireless sensor nodes are the devices of low data rate, low cost and low power. It is even more difficult in a mobile WSN where the nodes are moving in random directions. There are many more variables in a WSN. It requires extra resources and mechanisms. Currently, most of the discussions about mobile WSN are restricted to the sink nodes only. The rest of the nodes are not movable. 
         [0022]    This invention provides a soft state framework to support routing functionality in a fully mobile WSN where each node can move in random directions. This invention seeks to minimize the resource consumption in the design while delivering optimal functionality. 
         [0023]    The soft state approach is widely used in network signaling protocols. A soft state is maintained by periodical refreshment. The state goes away if it fails to receive the refreshment before a refreshing timer expires. There are a number of problems with existing soft state mechanisms: 
         [0024]    The refreshing messages go out of wire individually. This approach is inefficient and consumes too many system resources overall. 
         [0025]    The refreshing packets are sent randomly, which may generate traffic jitter. 
         [0026]    The refreshing packets can flood the network due to broadcast storms. As a result, many control packets can be lost. 
         [0027]    In a mobile WSN, the environment is highly dynamic because the nodes can move in random directions. This aspect requires seamless refreshing or updating. The current refreshing mechanisms do not support that. 
         [0028]    This invention provides innovative solutions to resolve all these issues associating with the refreshment in an efficient and elegant way. In particular, this solution is appropriate for a mobile WSN where the communications among the nodes are frequent. 
         [0029]    The new concepts defined in this invention include network elements, community, groups, subgroups, refreshing cycles and virtual socket. They are important building blocks for this invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0030]      FIG. 1  shows an embodiment of an exemplary wireless sensor network. 
           [0031]      FIG. 2  shows an embodiment of the assignment organization and distribution of a plurality of network elements. 
           [0032]      FIG. 3  provides an embodiment of the transfer of elements between groups and communities. 
           [0033]      FIG. 4  provides an embodiment of the present invention that reflects periodic refreshing of groups of a community based on a single timer. 
           [0034]      FIG. 5  provides an embodiment of the physical movement of node A in a wireless sensor network and the adjustment of network elements of nodes B, C, and D. 
           [0035]      FIG. 6  provides a chart of messages sent over time in a conventional soft refreshing configuration compared to messages sent over time of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0036]    The detailed description set forth below in connection with the appended drawings is intended as a description of presently preferred embodiments of the invention and does not represent the only forms in which the present invention may be constructed and/or utilized. The description sets forth the functions and the sequence of steps for constructing and operating the invention in connection with the illustrated embodiments. 
         [0037]    This invention provides an optimized soft state refreshing framework for mobile WSN routing. The solution maximizes the flexibility, reliability of the processes while minimizing the resource consumption. Specifically, this invention extends the mobility to every node in a WSN. 
         [0038]    This solution develops new mechanisms with a set of building blocks that shape the control traffic and smooth out the refreshing packets, thus effectively preventing the broadcast storms, packet losses and traffic jitters that are caused by the refreshment processes of the prior art. Further, this invention introduces entities such as a community, group, subgroup and refreshing cycles. With these building blocks, this solution creates new methodologies to overcome the shortfalls of existing approaches. 
         [0039]    With the building blocks, this invention supports seamless refreshment that will be required in a mobile WSN. Further, it provides a prudent timer mechanism to simplify the refreshing processes. 
         [0040]    The benefit of the virtual socket is to minimize the overhead of route advertisement without sacrificing the functionality. The combination of the beacon channel and socket channel ensure the completeness of the delivery service with the lowest cost. 
         [0041]    This invention seeks to distribute the network elements to different communities, groups, and subgroups. A network element is an entity that owns sufficient flavors to generate a specific refreshing message. A network element can be a signaling entry, routing entry, or a network entity that makes sense. In one embodiment, the network elements are data routes. 
         [0042]    In general, a collection of network elements that share the same attributes and refreshing time interval is distributed within a specific community. In one embodiment, the routing entries for adjacent nodes can be in one community. Their refreshing time interval is shorter than other communities. 
         [0043]      FIG. 1  shows an embodiment of a WSN. The WSN consists of a plurality of network nodes including routers, shown as circles; end devices shown as stars; and a sink node shown as a triangle. These nodes are in communication with each other. The sink node allows communication directly to a central computer, or out to the internet. The network nodes are impacted by environment events which are sensed by the nodes. 
         [0044]    Only the sink node and the router node have routing ability. Therefore, if every node in a WSN is mobile, then the WSN may have only the sink node and the router node, and may exclude the end nodes. However, in a WSN with some fixed nodes and some mobile nodes, end nodes may be utilized. As the present invention is directed to a routing protocol method, it is intended to be embedded in nodes with routing ability, i.e. sink nodes and router nodes. 
         [0045]      FIG. 2  shows an embodiment of the assignment organization and distribution of a plurality of network elements. A community consists of a collection of groups. A group represents a set of network elements for which the corresponding refreshing messages are sent at the same time. 
         [0046]    A group can be divided into subgroups. A subgroup represents a set of network elements for which the corresponding refreshing messages are encapsulated into one packet. The size of a subgroup is constrained by, for example, the Maximum Transition Unit (MTU) value of the local node or other factors. 
         [0047]    In  FIG. 3 , an embodiment of the transfer of elements from group to group is shown. The embodiment shown in  FIG. 3  shows the element B 2  transferred from group m to group  1 , thus the phase is shifted from m to  1 . The departing sequence of the groups is usually decided by group numbers. A network element can be transferred from one group to another dynamically. This feature allows an easy phase shift of refreshing cycle for an element. 
         [0048]    The total number of communities, groups, and subgroups varies from application to application. The network elements are distributed to the community based on their attributes. The assignment of the groups is based on the specific needs and the evenness of the distribution. In one embodiment, a newly created element can be placed in a group that departs immediately; an existing element can be transferred to an earlier group before its deletion. In another embodiment, both elements can be transferred similarly to what is shown in  FIG. 3 . The present invention uses its flexibility to balance the rapid distribution of updated network elements, and at the same time providing a substantially consistent number of message transmission at a given time interval. The flexibility of group assignment and transference creates the baseline for seamless, reliable refreshing/updating that is critical in a mobile WSN. 
         [0049]    The term attributes is defined herein to refer to specific characteristics of certain network elements. These specific characteristics are gathered in a community, and the community is configured to most efficiently address the needs of the elements with the similar characteristics. In one embodiment, the attributes of an element decide how frequently the element gets refreshed. An element that has attributes that require more frequent refreshing may be designated to a community that refreshes more frequently than other communities. 
         [0050]    In one embodiment where the network element is a route with a destination of a neighboring node, the route may have an attribute called “adjacent node”. This route may be assigned to an “adjacent node” community, which contains other network elements with adjacent node routes. This community may be refreshed relatively frequently because in the mobile WSN, an adjacent node affects a routing decision the most. 
         [0051]    In another embodiment for a WSN having some mobile and some fixed nodes, the fixed nodes may have a relatively stable route path. The network elements that are routes corresponding to the fixed nodes may have an attribute called “fixed node” and these routes may be assigned to a “fixed node” community. This community may be refreshed relatively infrequently because the fixed node routes are relatively stable and reliable. 
         [0052]    In an embodiment where the network element is a route with a destination of a mobile node, the route may be assigned to a “mobile node” community, which contains other network elements with mobile node routes. This community may be refreshed relatively frequently to moderately frequently. 
         [0053]      FIG. 4  illustrates the timer solution of the framework. The step adjuster adjusts the pace of the refreshing cycle by counting the number of the heartbeats. The number is adjustable. The refreshing cycle controls refreshing phases for each group. The refreshing cycles vary from community to community. Each refreshing cycle maintains a step account that increases when the step adjuster calls. The value of the step count is in a specific interval. The count starts over again once reaching its up boundary. Each value of the step count represents a slot that maps to a specific group. When the step count reaches the value of a slot, the corresponding group is refreshed, and sent to the adjacent nodes. 
         [0054]    In this invention, the routes are advertised by periodical refreshing that reflect the dynamic position of the nodes in a mobile wireless sensor network.  FIG. 5  shows an embodiment of the present invention that reflects this refreshing. In  FIG. 5 , node A is an arbitrary node in a WSN. It was originally located in top left corner. Node B sees it and advertises it via refreshing messages. Node A soon moves to the lower left corner. When node B notices the disappearance of node A (e.g. refreshing timeout), node B removes the element corresponding to the node A and optionally sends a delete message, therefore stopping the refreshing. In contrast, node C sees the node A and creates the element for it and inserts it to the appropriate community/group/subgroup. Therefore node C starts a refreshing cycle for node A. The new element corresponding to node A should be distributed to a group that is going to depart right away, because an earlier refreshment for node A minimizes the delay time for the adjacent nodes to gain the new routes reflecting the updates. The community/group/subgroup distribution mechanism provides an opportunity to shape the refreshing traffic in a desired way. 
         [0055]    In  FIG. 6 , an example of messages sent over time in a conventional soft refreshing configuration is shown. In  FIG. 6 , the horizontal axis represents the time sequence; the vertical axis represents the number of messages sent. The black dots represent the number of messages sent at specific time in conventional soft refreshing. Because the messages are sent randomly, there are no messages going out of wire at some times (e.g. T 1 , T 2 , T 3 , T 6 , T 7 , T 9 ). On the other hand, there might be a burst of messages (e.g. T 4 ) that causes traffic jam and loss of messages. In contrast, this invention is able to shape the refreshing traffic smoothly and evenly as it is showed in triangles. The present invention achieves this by evenly sending signals corresponding to the refreshing of substantially consistent sized groups, one group at a time. 
         [0056]    In a WSN, the electric power is a precious resource. The package transmission consumes significant amount of energy. Most nodes are battery powered, and conservation of energy directly results in longer life of a node. It costs several times the energy of what the CPU consumes at same time. In traditional soft refreshing, messages are sent one at a time, which is very electronically inefficient. With this invention, refreshing messages are always sent by groups; therefore, the energy usage is greatly minimized. 
         [0057]    Despite the number of communities, groups, subgroups, and network elements, only one timer is required in this invention. It greatly saves system resources. This timer is the heartbeat for all the refreshing cycles. The resolution of the timer is application specific; 1 second is the most common choice for applications. 
         [0058]    The present invention further creates a virtual socket that significantly reduces the overhead caused by refreshment traffic or routing advertisement. The virtual socket encapsulates the details of the delivery mechanisms. The virtual socket sends the packets in two ways. The first way uses regular sockets, another uses the payload field of a beacon packet. In this invention, the former is called socket channel, the latter is called beacon channel. The beacon channel piggybacks the refreshing packet for a “free” ride.  FIG. 1  provides an illustration of the virtual socket having a socket channel and a beacon channel. 
         [0059]    The beacon signals are sent regularly. In beacon channel, the signaling packets piggyback the routing information so that the overheads of routing advertisement are minimized. The beacon channel lacks flexibility since the signals are sent by its own logic. The problem with that is the routing packets cannot be sent at will when the routes are created/changed/deleted or the random events occur. The socket channel is used to resolve this issue. The idea is to use beacon channel as a first choice. If it is not available, the socket channel is used. It should be noted that the clients of the virtual socket are not aware of its underlying details. In one embodiment, the format of a beacon packet along with its payload follows the IEEE 802.15.4 standard. 
         [0060]    While several variations of the present invention have been illustrated by way of example in preferred or particular embodiments, it is apparent that further embodiments could be developed within the spirit and scope of the present invention, or the inventive concept thereof. However, it is to be expressly understood that such modifications and adaptations are within the spirit and scope of the present invention, and are inclusive, but not limited to the following appended claims as set forth.