Abstract:
A hybrid mobile ad-hoc network and a method of operating the same, including a mobile network node and a plurality of static network nodes randomly distributed over a coverage area with a predetermined density. The static network nodes form a static infrastructure backbone of the hybrid mobile ad-hoc network. Position information of the static network nodes, either through position awareness or triangulation with reference to other static nodes enhances the network function. The method tracks mobile node position with a minimum of overhead because of the fixed infrastructure of static nodes. The infrastructure can self-heal by placing excess static nodes in a hibernating state, and activating those in response to the failure of a nearby static node.

Description:
[0001]     The U.S. Government has a paid-up license in this invention and the right in limited circumstances to require the patent owner to license others on reasonable terms as provided for by the terms of Cooperative Agreement DAAD19-01-2-0011 with the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program. 
     
    
     BACKGROUND OF THE INVENTION  
       [0002]     1. Field of Invention  
         [0003]     The present invention relates to the field of telecommunication, and more particularly to the field of hybrid mobile ad-hoc networks.  
         [0004]     2. Description of Related Art  
         [0005]     Mobile Ad-hoc Networks (MANETs) are highly desirable to facilitate communication and message passing among mobile network nodes, for example those installed in vehicles and the like. Dynamically changing network topology due to node mobility and the resulting lack of a fixed network infrastructure make maintaining end-to-end connectivity in such networks a notoriously difficult problem despite tremendous effort.  
         [0006]     A variety of routing protocols have been proposed, among them Optimized Link State Routing (OLSR), Destination Sequenced Distance Vector (DSDV), Ad-hoc On-demand Distance Vector (AODV), Dynamic Source Routing (DSR), and GPS-based routing protocols.  
         [0007]     Each of OLSR, DSDV, AODV, and DSR requires nodes to maintain information about network topology. However, the dynamically and rapidly-changing nature of mobile network topology requires a flood of control messages among the nodes to maintain updated position information. Network bandwidth is quickly overwhelmed. As a result, such network protocols are inherently unscaleable.  
         [0008]     GPS-based routing protocols tend not to require global topology information. However, mobile nodes make routing decisions based upon knowledge of neighboring nodes, i.e. nodes within a one-hop distance with respect to transmission range. However, maintaining such knowledge would be extremely expensive in terms of network and computational resources in highly mobile environments.  
         [0009]     Fundamentally, previously proposed solutions do not use enough of the available information to optimize routing and network management decisions. Therefore, a mobile ad-hoc network capable of maintaining end-to-end communication with limited overhead would be desirable in the art.  
       BRIEF SUMMARY OF THE INVENTION  
       [0010]     It is an object of the present invention to provide a hybrid MANET which adapts well to dynamically changing mobile ad-hoc network environments and provides location-aware capability for resource-aware information dissemination. This is achieved by exploiting the existence of a subset of static nodes having a fixed, and more preferably known, position, thereby facilitating communication among the mobile nodes.  
         [0011]     It is a further object of the present invention to provide a hybrid MANET consisting of two types of network nodes: static network nodes and mobile network nodes. The static network nodes serve as an infrastructure backbone of the MANET. Mobile network nodes utilize the static network nodes to exchange information and to support a variety of location-aware applications.  
         [0012]     Therefore, according to the present invention, a hybrid mobile ad-hoc network includes a mobile network node and a plurality of static network nodes randomly distributed over a coverage area with a predetermined density. The static network nodes form a static infrastructure backbone of the hybrid mobile ad-hoc network. Preferably, at least two of the static network nodes are position-aware, with any position-ignorant static network nodes being located by triangulation from the position-aware static network nodes.  
         [0013]     Also provided according to the present invention is a method of operating a hybrid mobile ad-hoc network including a mobile network node, the method comprising randomly deploying a plurality of static network nodes over a coverage area in a predetermined density, determining the pair-wise network connectivity among the static network nodes in order to determine the network topography of an infrastructure backbone made up of the static network nodes, and communicating the infrastructure backbone topography information throughout the network. The method preferably further includes coordinating transmissions among neighboring static network nodes. In preferred embodiments, the method of the present invention utilizes the updated network topography information in making routing decisions.  
         [0014]     Preferably, at least two static network nodes are position-aware, the method further comprising determining the location of the position-aware static network nodes and any neighboring position-ignorant static network nodes, and including the location of the position-aware static network nodes in the network backbone topography information. Determining the relative position of neighboring static network nodes, can be accomplished by triangulation through ranging or directional position.  
         [0015]     In a preferred embodiment of the method, each static network node transmits a beacon at a periodic interval to advise other nodes of its existence, the periodic interval is an adjustable network parameter. Each mobile network node can respond to the beacon with a reply comprising information about the location of the mobile network node, including bearing information about the mobile network node. The reported location of each mobile network node can be communicated throughout the network.  
         [0016]     The static network nodes can be capable of operating in an active state and a hibernating state, entering the hibernating stated if it is determined that one or more of (a) a local static network node density exceeds a predetermined threshold, or (b) distance from another operating static network node is beneath a predetermined threshold. Any static network node operating in the hibernating state responds to the absence of an expected beacon from the nearest static network node in the active state by entering the active state. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0017]     These and other features, benefits and advantages of the present invention will be made apparent with reference to the following specification and accompanying drawing, in which like reference numerals indicate like features across the several views, and wherein:  
         [0018]      FIG. 1  illustrates aerial static node distribution in a hybrid MANET according to an exemplary embodiment of the present invention; and  
         [0019]      FIG. 2  illustrates a schematic plan view of a hybrid MANET according to an exemplary embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]     In order to maintain end-to-end connectivity in a MANET, according to the present invention a hybrid MANET includes a plurality of static network nodes and preferably one or more mobile network nodes. Referring now to  FIG. 1 , shown is a hybrid MANET, generally  10 , according to an exemplary embodiment of the present invention. A particular region or deployment area  20  is defined to be serviced and covered by the hybrid MANET  10 . A plurality of static network nodes  30  are populated in the deployment area  20 .  
         [0021]     The static network nodes  30  may be randomly located, and may be deployed by aerial drop, for example from a helicopter  40  or fixed wing aircraft. The density of static network nodes  30 , i.e., static network nodes per unit area, in the deployment area  20  may vary, taking into consideration the transmission range of static network nodes  30 , that of mobile network nodes  50  (See  FIG. 2 ), the terrain of the deployment area  20 , and/or the system requirements and motion speed of the mobile network nodes  50 . Alternately or additionally, static nodes may be deployed from ground-based vehicles, including being deployed from vehicles carrying mobile network nodes  50 . In this way the hybrid MANET  10  can adapt to conditions developing after initial deployment and setup, including for example unanticipated expansion of the deployment area  20 , or to improve connectivity and network performance.  
         [0022]     Once deployed, the static network nodes  30  initialize the hybrid MANET  10  to form a network infrastructure backbone. Referring now to  FIG. 2 , illustrated is a schematic plan view of a hybrid MANET  10  according to an exemplary embodiment of the present invention. Initialization includes determining the pair-wise network connectivity among these static network nodes  30  to define network infrastructure backbone topography.  
         [0023]     However, the performance of the hybrid MANET  10  is enhanced by knowledge of the position of each static node  30 . At least a subset of static network nodes  30  are position-aware static network nodes  30   a , which are capable of determining their position, for example by capability to receive GPS signals. Other forms of position determining capability are known in the art, for example by reference to known terrestrial radio beacons, or by inertial tracking, and may be used in place of or in addition to GPS. Once the location of a position-aware static node  30   a  has been established, the GPS or other position-locating means may be deactivated to conserve power in the position-aware static node  30   a.    
         [0024]     Once the position of a plurality of position-aware static network nodes  30   a  have been ascertained, any position-ignorant static network nodes  30   b  may be located by triangulation. Although described with reference to position-aware static network nodes  30   a , the relative position information among the static network nodes  30  is useful even in the absence of location information determined by position-aware static network nodes  30   a . Therefore, locating any or all static network nodes  30  is not a prerequisite to triangulation among the static network nodes  30 .  
         [0025]     Triangulation can be accomplished by approximating the range between static nodes  30  by reference to transmission power of messages received, and/or the timing of messages and response with respect to a network time slot allocation, described infra. Ranging triangulation between two position-aware static network nodes  30   a  can uniquely locate position-ignorant static network node  30   b  only at the mutual extent of transmission range with respect to each position-aware static network node  30   a . More likely, the intersection of radii with respect to two position-aware static network nodes  30   a  presents two potential locations. Ranging with respect to a third position-aware static network node  30   a  can uniquely locate the position-ignorant static network node  30   b.    
         [0026]     Alternatively, the position-aware network nodes  30   a , and optionally all static network nodes  30 , can have a directional antenna capable of determining the azimuth of a received message. In this case, only two such position-aware static network nodes  30   a  are required to uniquely locate a position-ignorant static network node  30   b . However, the directional antenna structure and associated direction decoding circuitry adds complexity, cost and weight to the static node  30 , and is less preferred.  
         [0027]     In any case, where static network nodes  30  are randomly distributed, it cannot be assured that two or three position aware static network nodes  30   a  as necessary are within the transmission range of a position-ignorant static network node  30   b . Therefore, in the preferred embodiments, all static network nodes  30  are position-aware static network nodes  30   a.    
         [0028]     According to the preferred embodiment, the now known and fixed position of static network nodes  30  determines the backbone topography of the hybrid MANET  10 . Backbone topography information may be stored and communicated throughout the network. Whether any static network nodes  30  are position-aware or not, overhead of establishing backbone topography need only occur once, and thereafter need not occupy bandwidth or computation resources with position updates.  
         [0029]     According to a further embodiment of the present invention, initialization of the hybrid MANET  10  includes coordination of transmissions among static network nodes  30 . Static network nodes  30  within transmission range of one another will negotiate or allocate time slots within a periodic cycle. Each static network node  30  will transmit its messages only during its designated time slot. Accordingly, the possibility of message collision is reduced, and network throughput along the infrastructure backbone is improved and increased. This transmission allocation schedule can include one or more unassigned allocations for a mobile node  50  to use as it passes in or out of transmission range of a static node  30 .  
         [0030]     With the hybrid MANET  10  backbone infrastructure established, each static node  30  broadcasts a beacon advising of its existence at some periodic interval. The interval is an adjustable network parameter, and can be responsive to the speed of mobile nodes in the network, to granularity (i.e., desired positional accuracy), or to desired responsiveness of the network. Upon receipt of such a beacon, mobile network nodes  50  reply with acknowledgment messages, including position information of the mobile node  50 , and preferably bearing information, more preferably at least speed and direction. The position information contained in the acknowledgement message is stored and disseminated across the infrastructure network.  
         [0031]     The present invention creates certain advantages over a conventional MANET. First, the static backbone topography of the hybrid MANET  10  assists in maintaining end-to-end network connectivity. Additionally, the mobile network nodes  50  are relieved from passing messages regarding the position of other nodes in the network, and from maintaining complete awareness of all or even nearby mobile network nodes  50  in the network. Similarly, the mobile network nodes  50  can easily and cheaply maintain knowledge of the network backbone.  
         [0032]     According to a preferred embodiment of the present invention, the position of each static node is known. Position information can provide location-aware and direction-aware routing capability to the mobile nodes. For example, the availability of location information about the static network nodes  30  can be used to anticipate the future location of mobile network nodes  50  by deriving bearing information about the mobile network node  50  from the location of static nodes  30  receiving sequential messages from given mobile nodes  50 . Alternately or additionally, even in the absence of position information regarding the static nodes  30 , the mobile network nodes  50  may provide bearing information in response to static network node  30  beacons. This, in turn, improves the efficiency and accuracy of message routing by predicting mobile node location without additional location information, for example by requesting a position query of the mobile network node  50 , which would consume additional network bandwidth.  
         [0033]     Further, knowledge of the position of static network nodes  30  allows direction-aware routing, i.e., passing a message in a different direction from which it came, rather than back in that same direction, to more efficiently propagate messages throughout the network. A received message header will preferably include information regarding the nodes through which it passed in addition to a destination. By reference to known backbone topography, a static node could deduce that a received message is destined in a different direction, and then not repeat that message, conserving bandwidth and improving overall network performance. Similarly, the known position of static network nodes  30  comprising the hybrid MANET backbone permits intelligent geographic forwarding among mobile network nodes  50 .  
         [0034]     Additionally, the hybrid MANET  10  according to the present invention has the ability to self-heal in response to the failure of a static node. Where static network nodes  30  are placed randomly, two or more static network nodes  30  may be so close to one another as to not appreciably add to network function. In such a case, a superfluous static node  30   c  may enter a hibernating state, in order to conserve power. In a hibernating state the static node  30  would receive messages, but not transmit or pass messages.  
         [0035]     Each static network node  30  is aware of its neighboring static network nodes  30  by receiving the periodic beacon emitted by a static network node  30  within a one-hop proximity (i.e., within broadcast range of the static network node  30 ). A predetermined threshold of local static network node density can be used to determine if an area is overcrowded. Alternately, if the position of each static network node is known, location proximity can be the determining threshold for overcrowding. If the number of received beacons exceeds the predetermined threshold, then the superfluous static network node  30   c  would enter a hibernating state. This determination typically takes place during the initialization of the hybrid MANET  10  infrastructure backbone.  
         [0036]     The absence of the expected periodic beacon from the static node  30   d  closest to the hibernating superfluous static node  30   c  can be interpreted as failure of the closest static node  30   d . In response, the superfluous static node  30   c  would transition from hibernating state to active state, and would begin to function as part of the hybrid MANET  10 . In this manner, the hybrid MANET  10  can self-heal from the failure of a static node  30   d.    
         [0037]     The present invention has been described herein with reference to certain exemplary embodiments. Certain modifications and alterations may be apparent to those skilled in the art without departing from the scope of the present invention. The exemplary embodiments are meant to be illustrative, and not limiting, on the scope of the present invention, which is defined solely with reference to the appended claims.