Travel characteristics-based ad-hoc communication network algorithm selection

A method of operating an ad-hoc communication system is provided. The method comprises determining a pattern type relating to mobile node travel characteristics over a defined traveling region. Based on the pattern type, selecting a neighbor discovery and route determination algorithm. Implementing the neighbor discovery and route determination algorithm on received location and identification mobile node information to determine communication routes to at least one of mobile nodes and stationary communication stations in the ad-hoc communication system.

BACKGROUND

Moving vehicles that that form ad-hoc communication networks to communicate between themselves require a means to determine neighbor vehicle locations in forming the ad-hoc communication network. One method used to determine neighbor vehicle locations is through message exchange wherein the messages include location information and ID information of the nodes (vehicles). Algorithms are applied to the received messages to perform neighbor discovery and routing determinations. However, the overhead (location and ID information) needed in each message for neighbor discovery and routing determinations can take up a large amount of the bandwidth. This limits the amount of other (payload data) that can be sent. Moreover, the complexity of algorithms can use up a lot of processing resources. It is desired to minimize the amount of bandwidth and processing resources used in forming an ad-hoc communication network so that resources can be freed up for other functions.

SUMMARY OF INVENTION

The above-mentioned problems of current systems are addressed by embodiments of the present invention and will be understood by reading and studying the following specification. The following summary is made by way of example and not by way of limitation. It is merely provided to aid the reader in understanding some of the aspects of the invention.

In one embodiment, a method of operating an ad-hoc communication system is provided. The method comprises determining a pattern type relating to mobile node travel characteristics over a defined traveling region. Based on the pattern type, the method continues by selecting a neighbor discovery and route determination algorithm. The final step in this method is implementing the neighbor discovery and route determination algorithm on received location and identification mobile node information to determine communication routes to at least one of mobile nodes and stationary communication stations in the ad-hoc communication system.

DETAILED DESCRIPTION

Embodiments of the present invention provide a method of efficiently implementing an ad-hoc communication network between moving vehicles that is based on select pattern types defined by vehicle traveling characteristics over a defined traveling region. In particular, in embodiments select algorithms are used for neighbor discovery and route planning based on the current traveling characteristics of neighboring vehicles over the then current traveling region. Although, the present invention is described as relating to aircraft it will be understood that any type of mobile nodes that exhibit predictable travel characteristics in relation to other mobile nodes over a traveling region can implement embodiments of the present invention to form an ad-hoc communication network.

Referring toFIG. 1, an ad-hoc communication network100of one embodiment is illustrated. In this embodiment, a plurality of aircraft104(1-N) and a ground station106make up the communication network100. In this example, the ground station106is to send a message to vehicle104-4via antenna108. However, vehicle104-4is beyond the communication range of the of the ground station106. To deliver the message to the intended vehicle, an ad-hoc communication network of the vehicles104(1-N) is formed. AsFIG. 1, illustrates, the ad-hoc communication network passes the message from vehicle104-5, which is in communication range of the ground station106, to vehicle104-2, then to vehicle104-3and then to destination vehicle104-4. The determination of the ad-hoc communication network between the vehicles104(1-N) (or nodes) is done with algorithms. In particular, algorithms are used to determine neighbor discovery and route determinations. In one embodiment, the vehicles exchange messages with overhead (location information and ID information of the nodes) to determine the topology of the network. In another embodiment, surveillance equipment in each node is used to provide all or a portion of the location and ID information. As discussed above, in embodiments, characteristics of the travel paths of the vehicles over a defined region are used to implement algorithms that are efficient based on the situation.

InFIG. 1, it is illustrated that the aircrafts104(1-N) are traveling in different paths in relation to each other. This is a situation that is encountered over a land mass206(a defined region) as illustrated inFIG. 2. InFIG. 2, an example of flight paths204over a land mass is illustrated. As this example illustrates, the flight paths204between hubs202(1-N) dictate that the aircraft (or nodes) will cross paths at all different angles. Hence, there is a high rate of neighbor change in this situation. Algorithms to determine topology and routing in this situation need to be fairly complex. In contrast,FIG. 3illustrates flight paths314(1-N) and322(1-N) over a body of water302such as an ocean302. Typically each flight path314(1-N) and322(1-N) is defined by points (latitude and longitude) through which the aircraft must pass in traversing over the ocean. In the example, ofFIG. 3, flight path314-1includes points308(1-N), flight path314-2includes points310(1-N), flight path314-N includes points312(1-N), flight path322-1includes points316(1-N), flight path322-2includes points318(1-N) and flight path322-N includes points320(1-N). In this type of arrangement, the aircraft are moving in a convoy-like behavior and although, aircraft may be flying at different altitudes, neighboring aircraft are typically moving in the same direction at about the same speed. Hence, knowing the characteristics of this situation, algorithms that determine neighbors and routing can be implemented that are not relatively complex. Moreover, in this situation, since neighboring aircraft are not going to change often, the algorithms need not perform neighbor discovery often. This frees up resources of the aircraft's communication system for other functions such as communicating payload messages.FIGS. 2 and 3illustrate examples of flight patterns that differ greatly. They are used to illustrate that different algorithms could be employed for neighbor discovery and routing. Other types of flight patterns are also contemplated, which will include specific algorithms defined to exploit their characteristics so that efficient and effective communication systems are created for each situation.

Referring toFIG. 4, a vehicle communication system400of one embodiment of a vehicle of the present invention is provided. In this embodiment, the communication system400includes an Aircraft Communication Addressing and Reporting System (ACARS) transceiver450which provides communication between the communication system400and a ground station via antenna452. The ACARS transceiver450is a data link communications transceiver that provides for the communication of relatively small messages via radio or satellite signals. Also included in the communication system is a communication transceiver414that communicates with other vehicles via antenna418. Further, the communication system400includes surveillance equipment401. The surveillance equipment401is used to transmit and receive, via the surveillance transceiver412and antenna416, at least position and ID information. Hence, the surveillance equipment401sends its position and its ID information and receives position and ID information from other aircraft surveillance equipment. This information is then used by other aircraft for collision avoidance reasons. In some embodiments, the surveillance information is also used to determine the position and ID information needed for neighbor discovery and route determination. In these embodiments, the position and ID information for the other aircraft is sent from the surveillance equipment401to the communications management function410. The communication system400includes a communication management function (CMF)410. The CMF410controls the functions of the communication system400. In embodiments of the present invention, the CMF410selects pattern type algorithms425used to determine topology of a communication network and routing paths based on the pattern type of airspace the communication system400is currently traversing.

As one skilled in the art will realize, it is not necessary to use surveillance equipment401, surveillance transceiver412and antenna416to determine position and ID information of other vehicles in the ad-hoc network, this information can be derived from information sent via antenna418and the communications transceiver414.

Moreover, as one skilled in the art will recognize, it is not necessary to have a separate ACARS transceiver450and antenna452as well as a communications transceiver414and antenna418. One of the at least combination ACARS transceiver450and antenna452and combination communications transceiver414and antenna418could serve as the air-to-air ad-hoc network communications path and the air-to-ground communications path.

In the case of aircraft, the avionics onboard the aircraft contain the information that serves as indicators to the CMF410of the type of airspace the aircraft currently occupies. In embodiments, this information may include but is not limited to an air traffic control message received by the ACARS transceiver450where message formats differ in each airspace, position data from the surveillance equipment (navigation equipment) in use with stored maps that set out boundaries for the types of airspace and passive monitoring of transmissions from neighboring aircraft via the communication transceiver414. In some embodiments the smooth transition between algorithms is employed where uninterrupted connectivity is essential. In one embodiment, uninterrupted connectivity is achieved by continuing to implement algorithms after a change in airspace is detected until a route is established by the algorithms designated for the then current airspace. In other embodiments uninterrupted connectivity is further achieved by switching to a new method and algorithms that yield better performance. This embodiment may be implemented where the network routing and algorithm selections for the airspace where determined as flawed.

FIG. 5illustrates an algorithm selection flow diagram500of one embodiment of the present invention. As illustrated, this process starts when a message needs to be sent via an ad-hoc network of vehicles, which in this example is aircraft (502). The type of airspace the aircraft is currently in is then determined (504). In one embodiment, the airspace type is continually monitored and determined by the CMF. An example of a method of determining the airspace is provided above. Next, algorithms based on the type of airspace are selected (506). A selected neighbor discovery algorithm is then implemented to determine the topology of the communication network (508). A selected route determination algorithm relating to routing paths is then implemented on the topology to determine the most efficient and reliable route (510). The message is then communicated via the selected route (512). In another embodiment, determining the type of airspace (504), selecting algorithms based on the airspace type (506), implementing the selected algorithm to determine neighbor discovery (508) and implementing the selected algorithm to determine the routing path to one of a select list of destinations or all destinations within the ad-hoc network (510), may operate as a periodically executed, message independent sequence of activities. In this embodiment, when a message is to be sent via ad-hoc network (502), the continuously operating subset of activities would provide the route to the destination and then the message would be sent via that routing path (512).