Travel characteristics-based ad-hoc communication network algorithm selection

(54) Title: METHOD OF OPERATING AN AD-HOC COMMUNICATION SYSTEM (30) Unionist Priority: 12/04/2007 us 11 / 950.218 (73) Title (s): Honeywell International INC (72) Inventor (s): DonaldC . Kauffaman (57) Abstract: A method of operating an ad-hoc communication system is presented. The method comprises the determination of a type of pattern related to the path characteristics of the mobile node over a defined path region. Based on the type of pattern, select a route determining algorithm and discovering neighbors. Implement the discovery of neighbors and the route determining algorithm on information from mobile nodes of identification and location received, to determine the communication routes for at least one of the mobile nodes and stationary communication stations in the ad-hoc communication system.

<img file="BRPI0809115A2_D0001.tif" />

ΡΙ0809115-3

METHOD OF OPERATING AN AD-HOC COMMUNICATION SYSTEM

Background of the Invention

Mobile vehicles, which form ad-hoc communication networks to communicate with each other, need a means to determine locations of neighboring vehicles in the formation of the ad-hoc communication network. One method used to determine locations of neighboring vehicles is through message exchange, where messages include location information and ID information of nodes (vehicles). Algorithms are applied to incoming messages to make routing and neighbor discovery determinations. However, the overhead (location and ID information) required in each message for routing and neighbor discovery determinations can consume a large amount of bandwidth. This limits the amount of others (load data) that can be sent. In addition, the complexity of the algorithms can use many processing resources. It is desired to minimize the amount of bandwidth and processing resources in the formation of an ad-hoc communication network, so that resources can be released for other functions.

For the reasons mentioned above and for other reasons mentioned below, which will become clear to people versed in the technique after reading and understanding this report, there is a need in the technique for an effective and efficient method to form and operate a network ad-hoc communication.

Summary of the Invention

The problems of the current systems mentioned above are addressed by the modality of the present invention, and will be understood by reading and studying the following report. The following summary is made for the purpose of example, and not for the purpose of limitation. It is simply presented to assist the reader in understanding some aspects of the invention.

In one embodiment, a method of operating an ad-hoc communication system is presented. The method comprises the determination of a type of pattern related to the path characteristics of moving nodes along a defined path region. Based on the type of pattern, Ό method proceeds, by selecting a route determining algorithm and discovering neighbors. The final step in this method is to implement the route determination and neighbor discovery algorithm, with respect to the received information of mobile identification and location nodes, to determine communication routes for at least one of the mobile nodes and stationary communication stations in the communication system. ad-hoc communication.

Brief Description of Drawings

The present invention can be more easily understood and its advantages and additional use become more easily evident, when considered in relation to the detailed description and the following figures, where:

fig. 1 is an illustration of an ad-hoc communication network of an embodiment of the present invention;

fig. 2 is an illustration of flight routes over a land mass;

fig. 3 is an illustration of flight paths over an ocean;

fig. 4 is a block diagram of the vehicle-to-vehicle communication system of an embodiment of the present invention; and fig. 5 is a flowchart for selecting algorithms, illustrating a method for implementing a modality of the present invention.

According to common practice, the various features described are not mapped to scale, but are designed to emphasize specific features relevant to the present invention. Reference characters indicate similar elements throughout the figures and the text.

Detailed Description

In the following detailed description, reference is made to the attached drawings, which form an integral part of this document, and where specific modalities are shown for purposes of illustration, in which the invention can be practiced. These modalities are described in sufficient detail to allow people skilled in the art to practice the invention, it should be clear that other modalities can be used, and that logical, mechanical and electrical changes can be made, without departing from the spirit and scope of the present invention. Thus, the following detailed description should not be considered in a limiting sense, and the scope of the present invention is defined only by the claims and their equivalents.

The modalities of the present invention present a method for efficiently implementing an ad-hoc network of communication between mobile vehicles, which is based on the selection of the types of patterns defined by vehicle travel characteristics over a defined travel region. In particular, in the modalities, selected algorithms are used for route planning and discovery of neighbors, based on the current route characteristics of neighboring vehicles along the current route region at the time. Although the present invention is described, as related to aircraft, it should be clear that any types of mobile nodes, which exhibit predictable path characteristics in relation to other mobile nodes along a path region, can implement modalities of the present invention, to form an ad-hoc communication network.

With respect to fig. 1, an ad hoc communication network 100 of one embodiment is illustrated. In this modality, a plurality of aircraft 104 (1-N) and a ground station

106 make up communications network 100. In this example, ground station 106 must send a message to the vehicle

104-4 via antenna 108. However, vehicle 104-4 is beyond the communication range of ground station 106. To transmit the message to the intended vehicle, an ad hoc network of vehicle 104 (1-N) is formed .

As shown in fig. 1, the ad-hoc communication network passes the message from vehicle 104-5, which is in the communication range of ground station 106, to the vehicle

104-2, after vehicle 104-3, and after destination vehicle 104-4. The determination of the ad-hoc communication network between the 104 (1-N) vehicles (or nodes) is done with algorithms. In particular, algorithms are used to define route determinations and discovery of neighbors. In one mode, vehicles exchange overloaded messages (location information and node ID information) to determine the network topology. In another mode, exploration equipment at each node is used to provide all or parts of the location and ID information. As discussed above in the modalities, characteristics of the vehicle's travel paths over a defined region are used to implement algorithms, which are efficient based on the situation.

In fig. 1 it is illustrated that aircraft 104 (1-N) are traveling in different paths, with respect to each other. This is a situation, which is found on a land mass 206 (a defined region), as illustrated in fig. 2. In fig. 2, an example of flight paths 204 over a land mass is illustrated. As this example illustrates, flight paths 204 between central stations 202 (1-N) dictate that the aircraft (or nodes) must cross paths at all different angles. Thus, there is a high rate of change of neighbors in this situation. Algorithms for determining topology and routing in this situation need to be quite complex. In contrast, fig. 3 illustrates flight paths 314 (1-N) and 322 (1-N) over a body of water 302, such as an ocean 302. Typically, each flight path 314 (1-N) and 322 (1- N) is defined by points (latitude and longitude), through which the aircraft must pass to cross the ocean. In the example in fig. 3, flight path 314-1 includes points 308 (1-N), flight path 314-2 includes points 310 (1-N), flight path 314-N includes points 312 (1- N), flight path 322-1 includes points 316 (1-N), flight path 322-2 includes points 318 (1-N), and flight path 322-N includes points 320 ( 1-N). In this type of arrangement, the aircraft is moving with a train-like behavior, and although the aircraft may be flying at different altitudes, neighboring aircraft are typically moving in the same direction and about the same speed. Thus, knowing the characteristics of this situation, algorithms that determine neighbors and routing can be implemented, which are not relatively complete.

Furthermore, in this situation, since neighboring aircraft will not make frequent changes, the algorithms do not need to frequently discover neighbors.

This frees up resources from the aircraft's communication system for other functions, such as communication load messages. Figs. 2 and 3 illustrate examples of flight patterns that differ considerably. They are used to illustrate, that different algorithms can be employed for neighbors discovery and routing. Other types of flight patterns are also contemplated, which should include specific algorithms defined to develop their characteristics, so that efficient and effective communication systems are created for each situation.

With reference to fig. 4, a vehicle-to-vehicle communication system 400 of a vehicle embodiment of the present invention is presented. In this modality, the communication system 400 includes an ACARS 450 transceiver, which provides communication between the communication system 400 and a ground station through antenna 452. The transceiver

ACARS 450 is a data link communications transceiver that provides relatively small message communication via radio or satellite signals.

Also included in the communication system is a communication transceiver 414, which communicates with other vehicles via antenna 418. In addition, the communication system 400 includes scanning equipment 401. Scanning equipment 401 is used to transmit and receive , via scanning transceiver 412 and antenna 416, at least position and ID information.

Thus, the scanning equipment 401 transmits its position and ID information, and receives position and ID information from other aircraft exploration equipment. This information is then used by the other aircraft to avoid collisions. In some embodiments, exploration information is also used to determine the position and ID information needed to determine the route and discover neighbors. In these modalities, the position and ID information for another aircraft is transmitted from the scanning equipment 401 to the communications management function 410. The communication system 400 includes a communications management function (CMF) 410. The CMF 410 controls the communication system functions 400. In embodiments of the present invention, CMF 410 selects pattern type 425 algorithms used to determine the topology of a communications network and routing paths, based on the type of airspace pattern, that communication system 400 is traversing at the time.

As a person skilled in the art should understand, it is not necessary to use scanning equipment 401, scanning transceiver 412 and antenna 416, to determine the position and ID information of other vehicles on the ad-hoc network, which information can. be derived from information sent via antenna 418 to communications transceiver 414.

In addition, as people skilled in the art should recognize, it is not necessary to have a transceiver

ACARS 450 and antenna 452, as well as a separate communications transceiver 414 and antenna 418. At least one combination of the ACARS 450 transceiver and antenna 452 and a combination of the communication transceiver 414 and antenna 418 can serve as an ad-hoc air / air network communication path and the air / ground communication path.

In the case of the aircraft, the avionics on board the aircraft contain the information, which serves as indicators for the CMF 410 of the type of airspace currently occupied by the aircraft. In the modalities, this information may include, but is not limited to, an air traffic controller message received by the ACARS 450 transceiver, where the message formats differ in each air space, position data through the exploration equipment (navigation equipment) in use with stored maps and set limits on the types of airspace and passive monitoring of transmissions from neighboring aircraft i

ί via the 414 communications transceiver. In some embodiments, a smooth transition between algorithms is employed, when uninterrupted connectivity is essential. In one mode, uninterrupted connectivity is achieved by continuing to implement the algorithms, after a change in airspace is detected, until a route is established by the algorithms intended for airspace at the time. In other modalities, uninterrupted connectivity is also achieved by changing to the new method and algorithms that produce better performance. This modality can be implemented when the routing selections and network algorithm for airspace are determined to be incorrect.

Fig. 5 illustrates a flowchart for selecting algorithm 500 of an embodiment of the present invention.

As illustrated, this process begins, when a message needs to be sent through an ad-hoc network of vehicles, which in this event is an aircraft (502). The type of airspace currently occupied by the aircraft is then determined (504). In one modality, the type of airspace is continuously monitored and determined by the CMF. An example of a method for determining airspace is presented 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 communications network (508).

An algorithm for determining the selected route, related to the routing paths, is then implemented in the topology, to determine the most efficient and reliable route (510). The message is then communicated via the selected route (512). In another modality, determining the type of airspace (504), selecting algorithms based on the type of airspace (506), implementing the selected algorithm to determine neighbor discovery (508) and implementing the selected algorithm to determine the routing path for one of a list of selected destinations or all destinations within the ad-hoc network (510), they can operate as a sequence of message-independent activities, periodically performed. In this modality, when a message has to be sent through the ad-hoc network (502), the subset of activities operating continuously must present the route to the destination, and then the message will be sent through this routing path (512) .

The methods and techniques used by CMF, as described above in algorithms to determine topology and routing paths, can be implemented in digital electronic circuits, or as a programmable processor (for example, a special processor or a general processor, such as a computer) , firmware, software, or a combination of these. The apparatus incorporating these techniques may include appropriate input and output devices, a programmable processor, and a storage medium that palpably incorporates program instructions for execution by the programmable processor. A process incorporating these techniques can be performed by a programmable processor, running an instruction program to perform desired functions, by operating on the input data and generating the appropriate output. The techniques can preferably be implemented in one or more programs, which are executable in a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system , at least one input device, and at least one output device. In general, a processor will receive instructions and data from a read-only memory and / or a random access memory. Suitable storage devices to palpably incorporate computer program instructions and data include all forms of non-volatile memory, including, for example, semiconductor memory devices, such as EPROM,

EEPROM, and flash memory devices; magnetic disks, such as internal hard drives and removable disks; magnetic optical discs; and DVD discs. Any of the above can be complemented by, or incorporated into, specially designed, specially designed integrated circuits (ASICs).

Although specific modalities have been illustrated and described here, it should be appreciated by people skilled in the art that any arrangement, which is calculated to achieve the same objective, can replace the specific modality shown. This application is intended to cover any adaptations or variations of the present invention. Thus, it is manifestly intended that this invention be limited only by the claims and their equivalents.