Adaptation protocols for local peer group (LPG) networks in dynamic roadway environments

A method and system for determining a size of a local peer group (LPG) network in a dynamic roadway (mobile) environment is provided. In one embodiment, the method comprises measuring a roundtrip time between a first node and a second node, and utilizing the measured roundtrip time to select the size of the local peer group network from a lookup table. In another embodiment, the method comprises determining when the roundtrip time exceeds a time interval of the heartbeat signal, and when the roundtrip time exceeds the time interval of the heartbeat signal adjusting the size of the local peer group network.

BACKGROUND

The present invention relates generally to wireless mesh networks, and more particularly to adaptation protocols for mesh networks in dynamic roadway environments.

A wireless mesh network is a communications network made up of radio nodes organized in a mesh topology. In a full mesh topology, each node is connected directly to each of the other nodes. In a partial mesh topology, nodes are connected to only some, not all, of the other nodes. The coverage area of the radio nodes working together as a single network is sometimes known as a mesh cloud. Wireless mesh networks can be implemented via various wireless standards, including 802.11, 802.16, and cellular technologies.

A mesh network provides the advantage of many-to-many connections between nodes, i.e., there is usually more than one possible route for communicating information between nodes. Mesh networks are also capable of dynamically updating and optimizing these connections. As new nodes become available they may be added to the mesh network. Nodes may also be removed from the mesh network. Thus, the topology of a mesh network is dynamic.

The nodes that form a mesh network may be highly mobile. For example, radio nodes may be part of an automobile or another type of motor vehicle that is constantly changing position. These nodes constantly roam (change position) within the mesh network. In addition, the size and topology of a mobile mesh network is constantly changing as nodes move in and out of a coverage area. The topology of a mobile mesh network changes even more frequently than the topology of a stationary mesh network.

Thus, there is a need in the art for protocols that define the topology of a wireless mesh network in a highly dynamic mobile environment.

SUMMARY OF INVENTION

A method and system for determining a size of a local peer group (LPG) network in a dynamic roadway (mobile) environment is provided. In one embodiment, the method comprises measuring a roundtrip time between a first node and a second node, and utilizing the measured roundtrip time to select the size of the local peer group network from a lookup table. In another embodiment, the method comprises determining when the roundtrip time exceeds a time interval of the heartbeat signal, and when the roundtrip time exceeds the time interval of the heartbeat signal adjusting the size of the local peer group network.

In one embodiment, the system comprises a processor operable to measure a roundtrip time between a first node and a second node and utilize the measured roundtrip time to select the size of the local peer group network from a lookup table. In another embodiment, the processor is further operable to determine when the roundtrip time exceeds a time interval of the heartbeat signal, and when the roundtrip time exceeds the time interval of the heartbeat signal adjusting the size of the local peer group network.

A computer readable medium embodying the method is also disclosed.

DETAILED DESCRIPTION

A method and system for determining an optimal size of a local peer group (LPG) network in a highly dynamic roadway (mobile) environment is provided. A dynamic roadway (mobile) environment refers to the constant flow of automobiles along streets and highways, as well as the direction of movement by the automobiles. An LPG network refers to a mobile mesh network that provides for wireless communication between automobiles within the network. The automobiles within the network are also known as “nodes”, and function in the same manner as nodes within a computer network. The invention is disclosed within the context of automobiles with radio transceivers functioning as the nodes within the LPG network. It is understood, however, that the invention and general concepts may benefit any computer network.

FIG. 1is an example of a topology of an LPG network. The topology comprises several automobiles (nodes) each having a wireless transceiver linked together to form the LPG network. The wireless transceiver may be part of a larger computer system within each automobile. This computer system is sometimes known as a “dashboard computer”. The dashboard computer comprises a memory and a processor and performs specific functions as directed by software stored within the memory. The wireless transceiver, which may be an 802.11 compliant transceiver and enables the automobiles and their respective dashboard computers to communicate with each other.

One of the automobiles102within the topology is labeled GH (“Group Header”). The group header is the “head node” within the topology, or the starting point from which the position of all the other automobiles (nodes) are measured. Automobiles114and116are one hop ahead of automobile (GH)102. Automobiles104and106are one hop behind automobile (GH)102. Automobiles108and110are two hops behind automobile (GH)102. Automobile112is three hops behind automobile (GH)102. A hop is defined as the number of connections between nodes required to reach the group header102. In instances where there is more than one possible path to the group header, the smallest hop count is used to define the relative relationship between the nodes. For example, automobile106may communicate directly with the GH102, or automobile106may communicate with the GH102via automobile104. When the automobile106communicates directly with the GH102, the hop count between these two automobiles is 1. When the automobile106communicates indirectly with the GH102via automobile104, the hop count between these two automobiles is 2. If the GH102is presented with an automobile that has one or more possible hop counts, e.g., automobile106, the GH102defines the relative position of that automobile according to the lowest hop count. Therefore, the relative position between the GH102and automobile106is defined by a hop count of 1.

FIG. 2is a TRmodel in accordance with one embodiment of the invention. TRis the total reporting time necessary for a node to respond to a heartbeat message from a GH102. THis the amount of time it takes for the individual automobiles to receive the heartbeat (HB) message from the GH102. TMis the amount of time it takes for the individual automobiles to send a message response (MR) to the GH102. TRis equal to THplus TM. TRis unique for each automobile. Generally, as the number of hops between an automobile and the GH102increases, the time value for TRalso increases.

TRmay also be estimated as follows according to equation 1:

TR=TH+TM=d+(h-1)⁢L_H+(2⁢Nh-1)⁢d+N⁡(h+1)2⁢d′=(h-1)⁢1-(1+Nh)⁢pNh+Nh⁢pNh+1(1-p)⁢(1-pNh)⁢d+2⁢Nh⁢d+N⁡(h+1)2⁢d′(1)
Wherein the above equation, h is the hop count, N is the number of nodes (automobiles), d is the heartbeat transmittal duration, d′ is the message response transmittal duration, and p is the probability of error. LHis the average per-hop HB forward latency, i.e., the average latency for the HB message to travel one hop; due to the random access contention to use the wireless channel, the HB message experiences a random latency to be forwarded at each hop), which is given by equation 2:

A heartbeat is a periodic signal generated by the GH102and transmitted (broadcast) to the other automobiles to determine if these automobiles are still present within the LPG. The GH102sends out heartbeat signals at regular intervals. Each automobile that receives the heartbeat signal rebroadcasts the heartbeat signal throughout the LPG. For example, as shown inFIG. 2, GH102broadcasts the heartbeat signal to automobile104; automobile104then rebroadcasts the heartbeat signal to automobile106. An automobile may remove itself from the LPG by roaming (driving) beyond the range of the heartbeat signal broadcast by GH102or by a driver turning off the automobile (which would also turn off the transceiver that receives the heartbeat signal). Automobiles may be added or removed to the LPG based upon their relative position (hop count) to the GH102. Upon receiving a heartbeat message from the GH102, an automobile responds with a message to the GH102acknowledging the heartbeat message. The acknowledgment indicates to the GH102that the responding automobile has received the heartbeat signal.

The heartbeat signal is a data packet that includes a “hop count” field. Every time the heartbeat signal is retransmitted, the hop count field is increased by one. If the frequency of the heartbeat signal is too small, then the overhead associated with the heartbeat signal will exceed a threshold limit because the LPG size is updated too frequently. Thus, there is a need for a method to select a heartbeat frequency and an LPG size in an efficient manner that does not over utilize system resources.

FIGS. 3 and 4together demonstrate how a “lookup table” can be created. The lookup table can be used to select an appropriate LPG size. Each time entry within the lookup tables shown inFIG. 3andFIG. 4is given in seconds.FIG. 3is an incomplete lookup table created from observed (measured) message responses as described below.FIG. 4is an estimated lookup table based uponFIG. 3. The missing lookup table time entries withinFIG. 4are calculated by a “least squares” approximation that utilizes the measured time entries in the lookup table ofFIG. 3. The use of a “least squares” approximation to calculate unknown values is well known in the art.

The estimated time entries within lookup table400can be used to select an appropriate LPG size. In one embodiment, the lookup table400is created by a simulator within the GH102. The following example utilizes a QUALNET™ 3.8 simulator to create the lookup table400. A GH102broadcasts a heartbeat signal every 1000 milliseconds (1 second). The heartbeat signal is broadcast in compliance with an 802.11a standard, at a data rate of 6 Mbps with an expected range of approximately 100 meters. It is assumed that an automobile, e.g., automobile104, receives the heartbeat signal within 300 milliseconds of the broadcast and responds with a message response (MR) including a node identifier and a hop count. There may be instances where the automobile104cannot communicate with the GH102because the communication channel is unavailable or blocked. In these instances, the automobile104waits 10 milliseconds, as a back off time period, and then attempts to communicate the MR to the GH102.

Once the MR is communicated from the automobile104to the GH102, the roundtrip time, TR, is calculated as discussed above and used to populate lookup table400. For example, a GH102broadcasts a heartbeat signal to an automobile104and the automobile104sends an acknowledgment, i.e., a message response back to the GH102. Further assume, for purposes of this example, that the automobile104is one hop away from the GH102and that roundtrip time is 0.014 seconds. Also assume that a second automobile108is two hops away from the GH102and returns a message response with a roundtrip time of 0.021 seconds. A third automobile106is only one hop away, but returns a message response with a roundtrip time of 0.024 seconds. These roundtrip times are used to populate lookup table300. Each roundtrip time is added to the lookup table300and associated with the appropriate number of hops. As the number of hops increases from 1 to 10, the roundtrip time also increases. An automobile may also be connected to the GH102by the same number of hops, but have a different roundtrip time. For example, automobiles104and106are both one hop away from the GH102, but the roundtrip time associated with automobile104is less than the roundtrip time associated with automobile106. The roundtrip times associated with a hop count increase from the smallest value to the greatest value moving from left to right across the lookup table300.

Estimated values for each missing table entry are calculated from the measured values in lookup table300utilizing the “least squares” approximation method. The use of approximation allows each entry in lookup table400to be completed. Lookup table400may then be used to select an appropriate LPG size.

In one embodiment, an LPG size is selected based upon a maximum TRvalue of 100 milliseconds (0.1 seconds). The TRvalue ensures the data passed between the automobile104and the GH102is “fresh” and relevant. Freshness is important in a dynamic roadway environment because it is desirable the GH102utilize only the most current data. An appropriate LPG size is selected from the lookup table400by selecting an LPG size associated with a time value less than 0.1 seconds and also constrained by the maximum number of hop counts. For example, if the maximum number of hop counts is set to five, then the selected LPG size is forty. Forty is the selected LPG size because it corresponds to an entry on the lookup table400with a maximum value that does not exceed 0.1, i.e., 0.097 and the maximum number of hop counts. As long as the automobile104is within five hop counts of the GH102, and there are forty or less automobiles within the LPG, the data passed between the automobile104and the GH102will be received in less than 0.1 seconds.

An important benefit of selecting an optimal LPG size from the lookup table400is the reduction in computational overhead associated with mathematically calculating the LPG size. An additional benefit comes from selecting an LPG size that ensures THis greater than TR. When TRis greater than TH, i.e., a second heartbeat signal is transmitted by the GH102before the MR is received. Any MRs received in response to the first heartbeat signal but after the second heartbeat signal is transmitted may supply irrelevant or inaccurate information to the GH102. Therefore, it is important that the MRs received at the GH102are in response to a heartbeat signal transmitted during that particular heartbeat cycle.

In one embodiment, the optimal LPG size is always associated with a maximum roundtrip time value less than a threshold value. As a GH102moves through the dynamic roadway environment, the topology of the LPG may constantly change as automobiles move in and out of communication range with the GH102. When the topology changes frequently, the frequency of the heartbeat signal is increased, i.e., the time interval between heartbeat signals is shortened to maintain freshness of the LPG. When the topology does not change, for example, the GH102and the surrounding automobiles are stopped at a red light or stalled in traffic, the frequency of the heartbeat signal is decreased, i.e., the time interval between heartbeat signals is lengthened.

FIGS. 5,6and7collectively disclose a method for determining an optimal LPG size.FIG. 5is a flow diagram of a method for determining an optimal LPG size.FIG. 6is a flow diagram of a method for determining an appropriate hop count value that is utilized by the method described byFIG. 5.FIG. 7is an alternative method for determining an appropriate hop count value that is utilized by the method described byFIG. 5.

The method starts at decision step501when a value for roundtrip time is calculated. In one embodiment, the roundtrip time is calculated as discussed above according to equation 1. At decision step502, a determination is made as to whether a roundtrip time exceeds a heartbeat time interval. If the roundtrip time does not exceed the heartbeat interval then the method proceeds to step508. The current size of the LPG network as well as the current hop count value is known and stored at the automobile inside the dashboard computer. At step508, the maximum hop count value is increased by 1. If the roundtrip time does exceed the heartbeat interval, then the method proceeds to step504.

At step504, the hop count value is evaluated and decreased by one of three methods. Two of the three methods that can be used to evaluate the hop count at step504are illustrated inFIG. 6andFIG. 7. In the third embodiment (not illustrated), the method utilizes a lookup table, such as one shown inFIG. 4, to select an appropriate hop count value based upon the roundtrip time as discussed above.

In the first embodiment, the hop count value is decreased by a value of 1. Referring toFIG. 6, which is an enlarged view of the process that takes place at step504, at step602a downsizing request associated with the hop count value is received by the dashboard computer. At decision step604, a determination is made as to whether the hop count value equals 1. If the hop count value equals 1, then the smallest possible hop count value has already been reached and the method ends. If the hop count value is greater than 1, then the method proceeds to step606. At step606, the hop count value is decreased by 1. The method illustrated byFIGS. 5 and 6together may be repeated to determine if an appropriate hop count value has been selected.

In another embodiment, the hop count value is factored, i.e., divided by a number to determine a new hop count value. Referring toFIG. 7, which is an enlarged view of the process that takes place at step504, at step702a downsizing request associated with the hop count value is received by the dashboard computer. In one embodiment, the hop count value is calculated as the midpoint value between the current hop count value and a lower bound value, such as zero. At step704, a lower bound value is stored in a variable L. In one embodiment, the lower bound value is set to zero. An upper bound value, i.e., the current hop count value (h), is stored in a variable R. The current hop count value (h) is divided by a factor, .e.g., 2, and the computed value is stored in variable x. For example, if the current hop count value is 10, and the value of the factor is 2, then 10 is divided by 2 to compute a value of 5. The value 5 is stored in the variable x. At step706, the roundtrip time is recalculated based upon the hop count value stored in the variable x. The roundtrip time calculated at step706should be less than the roundtrip time calculated at step501because the hop count value has decreased.

At decision step708, a determination is made as to whether the roundtrip time is now smaller than a threshold value, i.e., the heartbeat interval. If the roundtrip time is not smaller than the threshold value, the method proceeds to step710. At step710, the current hop count value stored in the variable x is also stored in the variable y. The hop count value stored in x is also restored into the variable R as the value of a new upper bound. Then the hop count value stored in the variable x is factored again. In one embodiment, a new hop count value is calculated according to the equation: x=[(R−L)/2] which provides a new midpoint value between the lower bound and the upper bound. The method then proceeds to decision step714, where a determination is made as to whether L<x<R. If L<x<R is true, then the method proceeds to step716and the hop count value is set to the value stored in the variable x. If L<x<R is false, then the method loops back to step706.

The following example illustrates how a hop count value of 10 may be reset to a hop count value of 3 by the method shown inFIG. 7. The hop count value stored in variable h is also stored in the variable R. R is the upper bound. The lower bound is set to zero and stored in the variable L. A new hop count value is computed as the value of the midpoint between the upper bound and the lower bound according to the equation x=[(R−L)/2]. After substituting in the values of the present variables, the equation may be rewritten as x=[(10−0)/2]=5. A new roundtrip time is calculated based upon a maximum hop count value of 5. However, a hop count value of 5, in this example, results in a roundtrip time that exceeds a threshold value, i.e., the heartbeat time interval. The current hop count value, 5, is refactored. The current hop count value 5 becomes the new upper bound, and L is still the lower bound. A new midpoint between the upper bound and the lower bound is recalculated. In the present example, the midpoint between the upper bound (R) and the lower bound (L) is calculated according to the equation x=[(R−L)/2]. After substituting in the values of the present variables, the equation may be rewritten as x=[(5−0)/2]=2.5. In one embodiment, when a non-whole number is computed as a value of a hop count, the number is rounded up. Therefore, 2.5 is rounded up to 3. A determination is then made as to whether the calculated hop count value, e.g., 3, is within the range of the lower bound and the upper bound. In the present example, the hop count value 3 is greater than the lower bound value of 0 and less than the upper bound value of 5. The new hop count value is set to 3 and used to compute a new roundtrip time.

Referring back to decision step708, if the roundtrip time is smaller than the threshold value, the method proceeds to step712. At step712, the value within the variable x is first stored in the variable y. Recall that the variable x stores the computed midpoint value between the upper bound and the lower bound of the original hop count value. The value stored in the variable x is then stored in the variable L. Finally, the value of the variable x is recomputed according to the equation x=L+[(R−L)/2]. As an example, assume that at step704, L is set equal to 0, h is set equal to 10, R is set equal to h, and x is calculated according to the equation x=[(R−L)/2] and found to have a value equal to 5. At step712, y=5, L=5, and x is recalculated according to the x=L+[(R−L)/2]. Substituting in the known values for each of the variables provides the equation x=5+[(10−5)/2] which gives a result x=7.5.

The method then proceeds on to step714. Again, using the results computed in the example from step712, a determination is made as to whether L<x<R is true. Substituting in the values for L, x, and R from step712, 5<7.5<10, which results in a true result, i.e., x lies between the lower bound and the upper bound. In one embodiment, the hop count value is rounded up from 7.5 to 8 because a hop count value must be a whole number. The method then loops back to step706, and the roundtrip time is calculated based upon the value of x.

FIG. 8is an example of a computing environment that can benefit from the present invention. In one embodiment, the computing environment comprises a GH102wirelessly in communication with another automobile104. The GH102and automobile104collectively form an LPG network. A dashboard computer802within the GH102controls the size of the LPG network and communication between the GH102and the automobile104. It is understood that the automobile104has a similar dashboard computer (not shown) capable of receiving and responding to communications received from the GH102.

The dashboard computer802comprises a processor (CPU)804, a transceiver806, and a memory808. The computer802is coupled to the transceiver806and the memory808and executes programs stored in memory such as “HB cycle control”814and “awareness components”810. The transceiver806enables wireless (RF) communication between the GH102and the automobile104. In one embodiment, the GH102communicates with the automobile104via the 802.11a standard. It is understood that the invention may use any wireless communication standard. Other components commonly found within a dashboard computer802, such as a power source, an antenna, a storage unit, and various support circuitry are understood to be present, but not shown inFIG. 8.

The memory808may include random access memory, read only memory, removable disk memory, flash memory, and various combinations of these types of memory. The memory808is sometimes referred to as a main memory and may in part be used as cache memory. The memory808stores at least the “awareness components”810, an LPG lookup table812, and the “HB cycle control”814. The awareness components810store the size of the LPG network and maintain a list of all the vehicles or automobiles within the LPG network. The awareness components810may also maintain information associated with each automobile within the LPG network. An example of the LPG lookup table814is provided inFIG. 4. The LPG lookup table814enables selection of an optimal LPG network size based upon the roundtrip time.

The “HB cycle control”814controls the maximum allowable hop count value between the GH102and the automobile104. The function of the “HB cycle control”814is described above in regards toFIGS. 5,6and7. In one embodiment, the “HB cycle control”814increases the hop count value when the roundtrip time is less than the heartbeat time interval. In another embodiment, the “HB cycle control”814decreases the hop count value when the roundtrip time is greater than the heartbeat time interval. Specific methods for decreasing the hop count value are described in regards toFIGS. 6 and 7. The “HB cycle control”814may also select an optimal LPG network size by utilizing a lookup table such as the one shown inFIG. 4.