Mobile ad-hoc network providing desired link delay offset without guard times and related methods

CROSS-REFERENCE TO RELATED APPLICATIONS

0001This application is a continuation-in-part of U.S. patent application Ser. No. 11/832,202 filed Aug. 1, 2007, the entire disclosure of which is hereby incorporated by reference herein.

FIELD OF THE INVENTION

0002The present invention relates to the field of wireless communications networks, and, more particularly, to mobile ad-hoc networks (MANETs) and related methods.

BACKGROUND OF THE INVENTION

0003Wireless networks have experienced increased development in the past decade. One of the most rapidly developing areas is mobile ad-hoc networks (MANETs). Physically, a MANET includes a number of geographically distributed, potentially mobile nodes sharing one or more common radio channels. Compared with other types of networks, such as cellular networks or satellite networks, the most distinctive feature of MANETs is the lack of any fixed infrastructure. The network is formed of mobile (and potentially stationary) nodes, and is created on the fly as the nodes communicate with each other. The network does not depend on a particular node and dynamically adjusts as some nodes join or others leave the network.

0004MANETs may use a variety of communications formats including Time Division Multiple Access (TDMA) arrangements. In TDMA-based MANET networks, nodes communicate during a specified time periods or time slots. To coordinate such communications, each node includes a clock which is synchronized with a highly stable time reference. For example, this stable time reference may be derived from a satellite-based GPS signal. Typical TDMA systems, such as cellular systems, often rely on synchronization to base stations to establish system timing and to compensate for propagation delay differences. Such centralized TDMA cellular systems include, but are not limited to, global systems for mobile communications (GSM), Integrated Digital Enhanced Network (iDENs) systems, 802.16 based broadband wireless access network systems, and TDMA satellite communications (SATCOM) systems.

0005One particularly advantageous wireless communication network which provides enhanced time slot allocation and interference avoidance/mitigation features is disclosed in U.S. Pat. No. 6,958,986, which is assigned to the present Assignee Harris Corporation and is hereby incorporated herein in its entirety by reference. The network includes a plurality of mobile nodes each including a wireless transceiver and a controller for controlling the wireless transceiver. The controller is also used for scheduling a respective semi-permanent time slot to establish a communication link with neighboring mobile nodes for transmitting data therebetween, where the data has different priority levels. The controller may also determine respective link utilization metrics for each data priority level for each communication link, and schedule demand assigned time slots for establishing additional communication links with the neighboring mobile nodes for transmitting data therebetween based upon the link utilization metrics and data priority levels. The wireless communication network may also provide enhanced interference avoidance and/or mitigation features in certain embodiments.

0006TDMA nodes can be expected to have a significant total time base uncertainty. Also, propagation delay between nodes can create additional timing uncertainties that change in real time as the mobile nodes move relative to one another. To manage these timing uncertainties, centralized cellular TDMA systems use a base station infrastructure to create a hub and spoke topology. These base stations are usually, but not necessarily, fixed in location. The mobile nodes operate as “spokes” or “clients” to the base station hubs and synchronize their transmissions to those base stations. However, a MANET is an infrastructure-less network that uses peer-to-peer control mechanisms, and therefore does not have base stations to provide a central timing reference.

0007In a TDMA MANET, an RF burst is usually transmitted within a time slot as close to the beginning of the time slot as possible. The time slot length may be selected to exceed the maximum RF burst length by an amount of time referred to as the “guard time.” A wireless TDMA system such as a MANET includes a controller that allocates these timeslots to different links based on criteria such as traffic demand and interference avoidance, thus sharing the available system bandwidth between links on a time shared basis.

0008Conventional MANET networks using TDMA generally allocate the timeslots by forming an access schedule which determines which link is allocated to which timeslot. These schedules are generally defined over some fixed interval often referred to as a TDMA epoch. A particular link may be granted one or more timeslots during an epoch.

0009When a traffic packet is available for transmission on a link, it waits until the timeslot assigned to that link before it can be transmitted. This time spent waiting for a timeslot is called “framing delay” and represents a large part of the transport latency encountered by a data packet as it transits in a TDMA MANET. In the case of a single timeslot assigned to a link per epoch, this wait time is half the epoch length on average and may be as long as the epoch on every hop through the network. Therefore, the length of a TDMA epoch largely determines the transit latency through the network.

0010To address this problem, some existing TDMA wireless systems have used very short epochs with only a few timeslots or very short timeslots or both. However, that approach limits the scalability of the network, increases the overhead of the network and increases the processing load of the TDMA controller. Other wireless TDMA systems allocate multiple slots to each link, which are distributed through the epoch. However if the time slots are distributed randomly that approach does not assure a lower delay and if they are distributed deterministically it is essentially the same thing as shortening the epoch.

0011It may therefore be desirable to provide a method for reliably reducing the framing delay of a wireless TDMA system, such as a TDMA MANET, for example, without requiring a shortened TDMA epoch.

SUMMARY OF THE INVENTION

0012In view of the foregoing background, it is therefore an object of the present invention to provide a mobile ad-hoc network (MANET) and related methods with desired link delay offset and without excessive guard times.

0013This and other objects, features, and advantages are provided by a MANET which may include a plurality of MANET nodes each including a wireless transceiver, a position determining device, and a controller cooperating with the wireless transceiver and position determining device for establishing a wireless communication link with an adjacent MANET node based upon a time division multiple access (TDMA) implementation. The TDMA implementation may use time slots without using a range dependent guard time therein. The controller may further determine a range to the adjacent MANET node, and schedule time slots to offset a link delay in a received signal from the adjacent MANET node based upon the determined range.

0014More particularly, an antenna may be coupled to the wireless transceiver. By way of example, the antenna may be a directional antenna, and the controller may establish a directional wireless communication link with the adjacent MANET node. Furthermore, the TDMA implementation may be a distributed TDMA implementation wherein time slot scheduling operations are shared between the MANET nodes. Additionally, the TDMA implementation may be a variable-length time slot TDMA implementation.

0015The controller may further cooperate with at least one neighboring MANET node when scheduling time slots to reduce a likelihood of interference. In addition, the controller may separately schedule transmit and receive time slots. Further, the controller may also determine an angle to the adjacent MANET node, and wherein the controller may schedule time slots based upon the determined range and the determined angle. The MANET nodes may also exchange respective positions with neighboring MANET nodes.

0016A MANET communications method aspect for a plurality of MANET nodes is also provided. The method may include establishing a wireless communication link between a pair of adjacent MANET nodes based upon a time division multiple access (TDMA) implementation. More particularly, the TDMA implementation may use time slots without using a range dependent guard time therein. The method may further include determining a range between the pair of adjacent MANET nodes, and scheduling time slots to offset a link delay in received signals between the pair of adjacent MANET nodes based upon the determined range.

BRIEF DESCRIPTION OF THE DRAWINGS

0017<figref idref="DRAWINGS">FIG. 1</figref> is a drawing that is useful for understanding timing problems which occur in mobile ad-hoc networks.

0018<figref idref="DRAWINGS">FIG. 2</figref> is a timing diagram that is useful for understanding timing problems which occur in mobile ad-hoc networks.

0019<figref idref="DRAWINGS">FIG. 3</figref> is a timing diagram that is useful for understanding timing problems which occur in mobile ad-hoc networks.

0020<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram of a wireless mobile node that can be used to implement the present invention.

0021<figref idref="DRAWINGS">FIG. 5</figref> is a timing diagram that is useful for understanding a timing relation between data epochs, mini-slots, and time slots.

0022<figref idref="DRAWINGS">FIG. 6</figref> is a drawing that shows a planar geometry of several nodes which is useful for understanding the invention.

0023<figref idref="DRAWINGS">FIG. 7</figref> is a timing diagram that is useful for understanding potential sources of interference in <figref idref="DRAWINGS">FIG. 6</figref>.

0024<figref idref="DRAWINGS">FIG. 8</figref> is a drawing that shows the planar geometry of several nodes in <figref idref="DRAWINGS">FIG. 6</figref> with different antenna pattern overlays.

0025<figref idref="DRAWINGS">FIG. 9</figref> is a timing diagram that is useful for understanding potential sources of interference in <figref idref="DRAWINGS">FIG. 8</figref>.

0026<figref idref="DRAWINGS">FIG. 10</figref> is a flowchart that is useful for understanding an interaction among various nodes in a mobile ad-hoc network.

0027<figref idref="DRAWINGS">FIG. 11</figref> is a flowchart that provides additional detail relating to step <b>1016</b> in <figref idref="DRAWINGS">FIG. 10</figref>.

0028<figref idref="DRAWINGS">FIG. 12</figref> is a flowchart that provides additional detail relating to step <b>1102</b> in <figref idref="DRAWINGS">FIG. 11</figref>.

0029<figref idref="DRAWINGS">FIG. 13</figref> is a flowchart that provides additional detail relating to step <b>1106</b> in <figref idref="DRAWINGS">FIG. 11</figref>.

0030<figref idref="DRAWINGS">FIG. 14</figref> is a flowchart that provides additional detail relating to step <b>1210</b> in <figref idref="DRAWINGS">FIG. 12</figref>.

0031<figref idref="DRAWINGS">FIG. 15</figref> is a flowchart that provides additional detail relating to step <b>1308</b> in <figref idref="DRAWINGS">FIG. 13</figref>.

0032<figref idref="DRAWINGS">FIGS. 16-18</figref> are flowcharts illustrating additional MANET communication method aspects of the invention.

0033<figref idref="DRAWINGS">FIG. 19</figref> is a time slot diagram illustrating time slot scheduling in accordance with the method illustrated in <figref idref="DRAWINGS">FIG. 18</figref>.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0034The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. Like numbers refer to like elements throughout, and prime notation is used to indicate similar elements in alternate embodiments.

0035Conventional approaches to peer-to-peer, ad-hoc TDMA communication networks are based on knowing only the maximum range between nodes. This concept is illustrated in <figref idref="DRAWINGS">FIGS. 1-3</figref>. <figref idref="DRAWINGS">FIG. 1</figref> shows a two-dimensional layout of a group of nodes in a prior art TDMA based mobile ad-hoc network (MANET). In <figref idref="DRAWINGS">FIG. 1</figref>, the transmitting node is node <b>102</b>. In this example, the system has a guard time that is designed to accommodate a maximum range indicated by the radius of the circle <b>103</b>. Nodes <b>104</b> are within this radius. Node <b>106</b>-<b>1</b> is outside this radius. Node <b>106</b>-<b>2</b> is further outside the radius as compared to node <b>106</b>-<b>1</b>.

0036Referring now to <figref idref="DRAWINGS">FIG. 2</figref> there is shown a conventional time slot <b>200</b>. The time slot has a duration <b>201</b>, a maximum RF burst time <b>202</b>, and a guard time <b>203</b>. The guard time is provided to accommodate range uncertainty as well as other timing uncertainties at the receiver and transmitter. An RF burst <b>206</b> is shown within the maximum burst time <b>202</b>. Referring again to <figref idref="DRAWINGS">FIG. 1</figref>, it will be understood that transmissions from node <b>102</b> to node <b>106</b>-<b>1</b> or <b>106</b>-<b>2</b>, which are of the maximum RF burst length, will contaminate the following (or later) time slot for node <b>106</b>-<b>1</b>, <b>106</b>-<b>2</b> because these nodes are each located beyond the radius of the maximum range circle <b>103</b>.

0037An alternative illustration of the foregoing concept is provided in <figref idref="DRAWINGS">FIG. 3</figref>. The transmit RF burst <b>206</b> of maximum length is shown in time slot n. At a node <b>104</b> the RF burst <b>206</b> arrives within slot n because node <b>104</b> is within the maximum guard time protected range. When RF burst <b>206</b> is received at a node <b>106</b>-<b>1</b> (beyond maximum protected range) the transmission will cause interference for node <b>106</b>-<b>1</b> in time slot n+1. At a more distant node <b>106</b>-<b>2</b>, the transmission will cause interference in time slot node n+2. As will be appreciated by those skilled in the art, transmitted RE bursts <b>206</b> that are not of maximum length may or may not contaminate the following time slot(s).

0038In <figref idref="DRAWINGS">FIGS. 1-3</figref>, the length of the guard period <b>203</b> can be defined so that it comprises a greater portion of the total time <b>201</b> comprising time slot <b>200</b>. Increasing the length of time of the guard period in this way can allow more distant nodes, such as nodes <b>106</b>-<b>1</b>, <b>106</b>-<b>2</b> to receive the RF burst <b>206</b> within the guard period for a time slot n. Thus, if it is known that the network must cover a larger area, a longer guard period can be selected. However, it will be appreciated that increasing the guard period in this way will decrease the time available for the RE burst <b>206</b>. This has the undesirable effect of reducing efficiency.

0039In the conventional TDMA MANET illustrated in <figref idref="DRAWINGS">FIGS. 1-3</figref>, the choice of which timeslots are assigned to which link is made using a “round-robin” or other time-sharing method known in the art. Typically a particular link receives one opportunity to access the radio resources and media each TDMA epoch. This has the undesirable effect of increasing the latency of the system.

0040The invention will now be described more fully hereinafter with reference to accompanying drawing <figref idref="DRAWINGS">FIGS. 4-15</figref>, in which illustrative embodiments of the invention are shown. This invention, may however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein.

0041In order to alleviate the deficiencies of the prior art, an embodiment of the invention includes a peer-to-peer TDMA type mobile ad-hoc network including a plurality of individual nodes. The individual nodes communicate with each other within an ad-hoc network environment. Significantly, information concerning the range between node pairs is estimated and exploited. Consequently, the scalability, latency, and efficiency of the TDMA communication system can be significantly enhanced.

0042The inventive arrangements advantageously include a distributed long range scheduler function as part of each node. The distributed long range scheduler determines specific times when node pairs can communicate to avoid interfering with one another. Heuristics produce an efficient distributed schedule for communication between node pairs. This schedule is advantageously based on information which includes both node range and angle (i.e., direction). Accurate time references are provided at each node and nodes exchange position estimates so that each node can maintain an estimate of range to its various neighbors.

0043Further, unlike conventional arrangements which provide a time axis measured in fixed time slots per epoch, the inventive arrangements may make use of a plurality of mini-slots. A plurality of mini-slots can be arbitrarily selected to define a time slot which is thereafter used for communications from one node to another node. The time slot may be independently evaluated by each node to determine whether its use will cause interference with neighboring nodes. Each node independently may adjust its schedule to account for the link delay. Further, transmit and receive time slots may be scheduled separately to allow for more efficient use of available time.

0044Referring now to <figref idref="DRAWINGS">FIG. 4</figref>, there is provided a simplified block diagram for a wireless mobile node <b>404</b> that is useful for understanding the present invention. The wireless mobile node can be used in a wireless communication network as described herein. The wireless mobile node <b>404</b> illustratively includes a directional antenna <b>403</b>, a transceiver <b>406</b>, and a control unit <b>408</b>. The wireless mobile node <b>404</b> can optionally include an omni-directional antenna <b>402</b>.

0045The transceiver <b>406</b>, the omni-directional antenna <b>402</b> and the phased array antenna <b>404</b> collectively enable wireless communications between the wireless mobile node <b>404</b> and a plurality of other nodes having a similar configuration in the MANET. In this regard, it should be appreciated that the omni-directional antenna <b>402</b> is configured to send and/or receive signals in any direction. The directional antenna <b>403</b> is configured to selectively send and/or receive signals in a desired direction. The directional antenna <b>403</b> can include, but is not limited to, a phased array antenna. The omni-directional antenna <b>402</b> and directional antenna <b>403</b> are coupled to the transceiver <b>406</b> so that RF signals can be communicated to and from each of these antennas. In an alternative embodiment, the omni-directional antenna can be omitted and omni-directional communications can be provided by scanning a directional antenna beam through a wide range of azimuth and elevation angles.

0046The transceiver <b>406</b> can include conventional RF circuitry (not shown) and a modem (not shown) for receiving and transmitting RF signals. The transceiver <b>406</b> is electrically connected to the control unit <b>408</b> so that received signals demodulated by the transceiver <b>406</b> can be communicated to the control unit. Similarly, baseband digital data and control signals can be communicated from the control unit <b>408</b> to the transceiver <b>406</b>.

0047The control unit <b>408</b> illustratively includes a processor <b>410</b>, antenna control unit <b>412</b>, clock <b>414</b>, and node position unit <b>416</b>. The antenna control unit <b>412</b> can control a direction of an antenna beam associated with the directional antenna <b>403</b>. The antenna control unit <b>412</b> can optionally be included as part of the transceiver <b>406</b>. Clock <b>414</b> provides a highly accurate and stable time reference for each node. The accuracy of the clock <b>414</b> can be maintained by various timing approaches. For example, a GPS timing signal can be used for this purpose. As will be appreciated by those skilled in the art, GPS timing signals can provide a highly accurate time reference. Thus, clock <b>414</b> can be synchronized with clocks of other wireless mobile nodes forming part of the network described herein. The clocks are preferably synchronized to within a fractional portion of a mini time-slot (described below in greater detail). According to one embodiment, the time references can advantageously be selected so that a clock <b>414</b> associated with each node <b>404</b> is synchronized to within 100 nanoseconds of other nodes in the network. Still, the invention is not limited in this regard.

0048The control unit <b>408</b> also illustratively includes a node position unit. The node position unit is configured to allow the node to identify its position. For example, the node position unit can advantageously include a GPS receiver and GPS processing circuitry suitable for allowing the node <b>404</b> to precisely locate its position at any terrestrial or airborne location. If a GPS receiver is used, the GPS timing data can be used as described above to aid in synchronizing the clocks <b>414</b> in each of the nodes <b>404</b>.

0049The control unit <b>408</b> also includes a memory device <b>450</b>. The memory device <b>450</b> stores several different types of information. For example, the memory device <b>450</b> can includes a neighbor information table <b>420</b>, epoch schedule <b>422</b>, a receive (Rx) interference profile <b>424</b>, a transmit (Tx) interference profile <b>426</b>, and a neighbor time-slot usage profile <b>428</b>. The various types of information stored in memory device <b>450</b> will be discussed below in greater detail. The various components forming the control unit <b>408</b> can communicate with each other by a suitable data bus <b>418</b>.

0050Those skilled in the art will appreciate that the architecture described herein for wireless mobile node <b>404</b> is one possible example of a wireless mobile node which can be used with the present invention. However, it should be understood that the invention is not limited in this regard. Instead, any other suitable wireless mobile node architecture can also be used without limitation.

0051An overview of the basic operation of wireless mobile network utilizing a plurality of wireless mobile nodes <b>404</b> according to the inventive arrangements will now be provided. According to an embodiment of the invention, individual network nodes <b>404</b> use a neighbor discovery process. The neighbor discovery process includes an exchange of position information so that each node has the coordinates of neighboring nodes. This position information allows the range information and relative direction of such neighbor nodes to be calculated. Range information and direction information is used for purposes of performing interference calculations. Interference calculations also include consideration of propagation delays between nodes and required antenna beam pointing directions based on the known node locations. Interference calculations may also utilize time slot allocations at other nodes, both transmit and receive, as well as the directions the transmit and receive antennas are pointing.

0052The present invention is unlike conventional MANET systems that utilize conventional TDMA technology. In such conventional TDMA systems, periods of time are divided into epochs, and communication between nodes occurs in time slots which are sub-portions of each epoch. Significantly, each time slot in a conventional system will have a fixed timing position in each epoch. Nodes in the ad-hoc network which need to communicate are assigned time slots for such communications. However, this fixed timing creates problems for long range communications.

0053The present invention also divides time into a series of epochs. However, the timing of the time slots used for communications between nodes is not fixed. Stated differently, it can be said that the timing position of each time slot is not fixed within each epoch. In the present invention, the position of time slots within each epoch can be arbitrarily selected by the nodes in accordance with an algorithm. The algorithm is selected for minimizing potential interference among neighbor nodes.

0054In order to allow for time slots to have timing positions which are arbitrarily defined within an epoch, the present invention introduces the concept of mini-slots, which are combined to form a time slot. For example, any number of mini-slots can be combined to form a time slot. This concept can be better understood with reference to <figref idref="DRAWINGS">FIG. 5</figref>. In <figref idref="DRAWINGS">FIG. 5</figref>, there is shown a timing diagram <b>500</b> for a TDMA type mobile ad-hoc network according to the inventive arrangements. The timing diagram shows a series of data epochs <b>504</b> which are fixed divisions of time. Each epoch <b>504</b> is sub-divided into a plurality of N mini-slots <b>506</b>. According to an embodiment of the invention, a time slot <b>508</b> can be comprised of contiguous groups of M mini-slots. For example, a typical time slot <b>508</b> can be comprised of 8 mini-slots <b>506</b> (M=8). Each time slot <b>508</b> can have an arbitrarily defined starting position (subject to interference calculations) that corresponds to a starting time of any selected mini-slot. Each time slot <b>508</b> can have different lengths by combining 1, 2, 3, 4, or more mini-slots.

0055In order to understand how time slot timing, range, direction and propagation information is used to mitigate interference, an example is useful. <figref idref="DRAWINGS">FIG. 6</figref> shows a planar geometry of several nodes where node <b>4042</b> (the transmitting node) is attempting to schedule a transmit time slot consisting of five mini-slots (M=5) with node <b>4046</b> (the receiving node). In <figref idref="DRAWINGS">FIG. 6</figref>, the transmit beam pattern <b>602</b> is shown for node <b>2</b>. Nodes <b>4044</b>, <b>4046</b>, <b>4047</b> and <b>4049</b> are located within range and in the beam pattern. A time slot scheduler can be used to automatically select a timing position for a transmit time slot that will minimize interference to neighboring nodes.

0056The scheduler process begins by selecting a candidate set of mini-slots which will define the position of the transmit time slot for node <b>4042</b>. <figref idref="DRAWINGS">FIG. 7</figref> is a timing diagram <b>700</b> which shows the time base at nodes <b>4042</b>, <b>4044</b>, <b>4046</b>, <b>4047</b> and <b>4049</b>. It is assumed that clocks <b>414</b> at the nodes <b>4041</b>-<b>4049</b> are synchronized to fractions of a mini-slot.

0057The timing diagram shows that a candidate set of mini-slots MT<b>2</b>-MT<b>6</b> can be selected at node <b>4042</b> which define a possible timing position for time slot <b>702</b>. In order to determine whether this timing position will cause interference with neighboring nodes, the timing position of time slot <b>702</b> is mapped to the corresponding time intervals at nodes <b>4044</b>, <b>4046</b>, <b>4047</b> and <b>4049</b>. These corresponding time intervals <b>704</b>, <b>706</b>, <b>707</b>, <b>709</b> are offset from time slot <b>702</b> because of the propagation delay “d” between the nodes. Propagation delay can be determined if the transmitting node <b>4042</b> knows the relative position of neighbor nodes <b>4046</b>, <b>4047</b> and <b>4049</b>. The corresponding time interval for the receiver node <b>4044</b>, is <b>704</b>. The corresponding time intervals mapped to the location of nodes <b>4046</b>, <b>4047</b> and <b>4049</b> are respectively <b>706</b>, <b>707</b>, <b>709</b>. Time intervals <b>706</b>, <b>707</b>, <b>709</b> represent the time intervals at nodes <b>4046</b>, <b>4047</b> and <b>4049</b> during which the signal will arrive from node <b>4042</b> if transmitted during time slot <b>702</b>.

0058It should be understood that during the time intervals <b>706</b>, <b>707</b>, <b>709</b>, a transmitted signal from node <b>4042</b> will cause interference at nodes <b>4046</b>, <b>4047</b> and <b>4049</b> if the antenna beams of these nodes are pointed in the direction of transmitting node <b>4042</b>. For example, it can be observed that transmitting node <b>4042</b> can be within a receive antenna beam <b>606</b> of node <b>4046</b> during a transmit time interval. Notably, transmitting node <b>4042</b> can advantageously be provided with position and timing schedule for neighbor nodes to determine the direction in which its neighbor node antennas are pointing during each mini-slot. If transmitting node <b>4042</b> determines that any one of nodes <b>4046</b>, <b>4047</b> and <b>4049</b> are in fact scheduled to receive signals (1) from a direction which coincides with transmitting node <b>4042</b>, and (2) such signals are scheduled to be received during the intervals <b>706</b>, <b>707</b>, <b>709</b>, then it can conclude that the transmissions from node <b>4042</b> during time slot <b>702</b> will cause interference. If transmitting node determines that interference will occur, then a different candidate time slot <b>702</b> is advantageously selected.

0059If node <b>4042</b> determines that time slot <b>702</b> will not cause interference to the receivers of nodes <b>4046</b>, <b>4047</b> and <b>4049</b> then a second analysis can be performed. This second analysis can determine whether any nodes in the antenna beam of receiver node <b>4044</b> will be transmitting in the direction of node <b>4044</b> during the time interval corresponding to time slot <b>702</b> (as adjusted for propagation delay). This analysis is shown in <figref idref="DRAWINGS">FIGS. 8 and 9</figref>. <figref idref="DRAWINGS">FIG. 8</figref> shows a planar geometry <b>800</b> which is similar to the one shown in <figref idref="DRAWINGS">FIG. 6</figref>. However, in <figref idref="DRAWINGS">FIG. 8</figref>, nodes <b>4046</b>, <b>4047</b> and <b>4049</b> are omitted for greater clarity since they are not part of this analysis. It can be observed in <figref idref="DRAWINGS">FIG. 8</figref> that nodes <b>4041</b>, <b>4042</b>, <b>4043</b> and <b>4045</b> are located within the range and in the receiver beam pattern <b>812</b> of node <b>4044</b>.

0060<figref idref="DRAWINGS">FIG. 9</figref> shows a timing diagram which includes segment of the time base at several nodes <b>4041</b>-<b>4045</b>. It is assumed that clocks <b>414</b> at the nodes <b>4041</b>-<b>4044</b> are synchronized to fractions of a mini-slot. In <figref idref="DRAWINGS">FIG. 9</figref>, the timing position of time interval <b>704</b> is mapped to the corresponding time intervals at nodes <b>4041</b>, <b>4043</b>, and <b>4045</b>. These corresponding time intervals <b>901</b>, <b>903</b>, <b>905</b> are offset from time slot <b>704</b> because of the propagation delay “d” between the nodes. <figref idref="DRAWINGS">FIG. 9</figref> shows that node <b>4044</b> will experience interference during time interval <b>704</b> if nodes <b>4041</b>, <b>4043</b>, or <b>4045</b> transmit toward node <b>4044</b> during time periods <b>901</b>, <b>903</b>, or <b>905</b>. If node <b>4044</b> has transmission schedules and position information for nodes <b>4041</b>, <b>4043</b>, or <b>4045</b> then it can determine whether time interval <b>704</b> is an acceptable receive time for node <b>4044</b>. In the same way, node <b>4044</b> can determine whether time interval <b>702</b> is an acceptable transmit time slot for node <b>4042</b>.

0061The flowcharts in <figref idref="DRAWINGS">FIGS. 10-14</figref> will now be used to explain how the concepts discussed above in relation to <figref idref="DRAWINGS">FIGS. 6-9</figref> can be applied in a mobile ad-hoc network. <figref idref="DRAWINGS">FIG. 10</figref> provides a basic overview of a mobile ad-hoc network process <b>1000</b>. It will be understood that the scheduler process described in relation to <figref idref="DRAWINGS">FIGS. 6-9</figref> requires detailed information regarding the identification, position, and communication schedule of neighbor nodes. Process <b>1000</b> is useful for understanding how such information is exchanged. Still, it should be understood that the process <b>1000</b> merely discloses one possible process for exchange of such data and the invention is not intended to be so limited. Instead, any other process for exchanging node identification, position, and communication schedule can be used. Further, it should be understood that all of the foregoing information can be exchanged using one or more control channels. For example, one or more mini-slots can be defined as control channels which are reserved for exchange of such information.

0062The process <b>1000</b> begins in step <b>1002</b> and continues with step <b>1004</b>. In step <b>1004</b>, nodes in a network engage in a neighbor discovery process. Neighbor discovery processes in mobile ad-hoc networks are generally well known. Accordingly, the details of this process will not be described here. However, it should be understood that the neighbor discovery process involves transmission of “hello” messages to neighboring nodes using a control channel. The “hello” message can be broadcast to neighboring nodes by any suitable means. For example, the “hello” message can be transmitted by using an omni-directional antenna <b>402</b> or a scanned beam provided by directional antenna <b>403</b>.

0063The “hello” message can include node identifier information and a position report for the node which transmits the message. Each node determines its own position using the node position unit <b>416</b>. Each node also collects identifying information and position information from its neighbors using these “hello” messages.

0064In step <b>1006</b>, information derived from the neighbor discovery process in step <b>1004</b> is used to populate (and/or update) neighbor information tables at each node. For example, node identification and position information can be stored in a neighbor information table <b>420</b>. Each node further maintains an epoch schedule <b>422</b> which provides timing information for the occurrence of each data epoch <b>504</b>. Timing of mini-slots <b>506</b> can also be derived from the epoch schedule <b>422</b>.

0065The network process <b>1000</b> continues with step <b>1008</b> in which each node periodically communicates to its neighbors a transmit schedule or portion of the transmit schedule indicating changes since the last schedule update for that node. In step <b>1010</b>, each node also periodically broadcasts to its neighbors a receive schedule or portion of the receive schedule indicating changes since the last schedule update for that node. In step <b>1012</b>, each node stores neighbor transmit and receive information in the table in <figref idref="DRAWINGS">FIG. 4</figref> identified as the neighbor time slot usage profile <b>428</b>.

0066The process continues in step <b>1014</b> in which each node uses processor <b>410</b> to apply topology control rules to the information stored in its neighbor information table <b>420</b>. The topology control rules can be stored in memory device <b>450</b>. The topology control rules are used to select one or more neighbor nodes with which communication links should be established. Topology control rules for mobile ad-hoc networks are well known in the art and therefore will not be described here in detail. However, it should be understood that such topology control rules can allow a node to determine whether communication links with various neighbor nodes should be established, maintained, or terminated.

0067In step <b>1016</b>, new communication links are formed with selected neighboring nodes as determined by the topology control rules. This process of forming links with new nodes will be described in more detail in relation to <figref idref="DRAWINGS">FIGS. 11-14</figref>. In step <b>1018</b>, certain communication links are terminated with selected neighbor nodes as determined by topology control rules. In step <b>1020</b>, a determination is made as to whether the network process should be terminated for any reason. If so, then the process terminates in step <b>1022</b>. Alternatively, the process continues with step <b>1004</b> and repeats.

0068<figref idref="DRAWINGS">FIG. 11</figref> shows a series of steps which provide further detail concerning step <b>1016</b> in <figref idref="DRAWINGS">FIG. 10</figref>. Step <b>1016</b> involves one node forming a communication link with a selected neighbor node. Establishing this communication link begins with selection of a suitable time slot when a first node (transmitter node) will transmit data to a second node (receiver node).

0069As shown in <figref idref="DRAWINGS">FIG. 11</figref>, step <b>1016</b> includes a series of steps which can begin with step <b>1102</b>. Step <b>1102</b> includes using a scheduler process at the transmitter node to generate a list of candidate transmit time slots for transmissions from the transmitter node to the receiver node. The scheduler process can be performed by processor <b>410</b> executing a programmed set of instructions. Alternatively, the scheduler process can be implemented as any other combination of hardware and software. Step <b>1102</b> is described in greater detail in <figref idref="DRAWINGS">FIG. 12</figref>. In general, however, the list of candidate time slots can be generated using an interference analysis similar to that described in relation to <figref idref="DRAWINGS">FIGS. 6-7</figref> which accounts for the distance between the transmitting and receiving node. In this regard it may be noted that in <figref idref="DRAWINGS">FIGS. 6 and 7</figref> the transmitter node was node <b>4042</b> and the receiver node was <b>4044</b>.

0070In step <b>1104</b>, the list of candidate transmit time slots can be communicated from the transmitter node to the receiver node. Any suitable means can be used for communicating this candidate transmit time slot list from the transmitter node to the receiver node. For example, a dedicated control channel can be used for this purpose. Still, the invention is not limited in this regard.

0071In step <b>1106</b>, the candidate transmit time slot list is received and used at the receiver node to determine which of the proposed candidate time slots are acceptable. Step <b>1106</b> is described in greater detail in <figref idref="DRAWINGS">FIG. 13</figref>. In general, however, acceptable candidate time slots can be determined using a process similar to that previously described in relation to <figref idref="DRAWINGS">FIGS. 8-9</figref>. Following steps <b>1106</b>, the receiver node will now be aware that transmitter node wishes to establish a transmit time slot for communications to receiver node. Consequently, the receiver node can initiate another process similar to that described in step <b>1016</b> for the purpose of establishing a transmit time slot for communications from the receiver node to the transmitter node. To avoid redundancy, that process will not be described here.

0072Continuing on now with step <b>1108</b>, a message can be sent from the receiver node to the transmitter node. The message identifies those transmit time slots proposed by the transmitter node which are determined to be acceptable to the receiver node. In step <b>1110</b>, this message is received at transmitter node. The process continues on to step <b>1112</b> in which the receiver node begins listening for transmissions from the transmitter node during the time slot which has been accepted by the transmitter node. The time at which the receiver begins to listen for the transmission from the transmitter node is delayed from the beginning of the time slot by the distance between the transmitting and receiving node. Although not required, it may be desirable for the receiver to begin listening slightly before the expected time to account for uncertainties in the network timing and node positions. In step <b>1114</b> data transmissions can begin from the transmitter node to the receiver node using the time slot that has been selected. Thereafter, the process can continue on to step <b>1018</b> as previously described.

0073Referring now to <figref idref="DRAWINGS">FIG. 12</figref>, there is provided a more detailed description of the processes associated with step <b>1102</b> in <figref idref="DRAWINGS">FIG. 11</figref>. Step <b>1102</b> involves using a scheduler process at the transmitter node to generate a list of candidate transmit time slots for transmissions from the transmitter node to the receiver node. As an aid to understanding, step <b>1102</b> will be described with reference to <figref idref="DRAWINGS">FIG. 5</figref>.

0074The process can begin with step <b>1202</b> in which the scheduler process at the transmitter node selects a candidate transmit time slot beginning at mini-slot n and comprised of M mini-slots that are contiguous with each other. For example, in <figref idref="DRAWINGS">FIG. 5</figref> a candidate time slot can be time slot <b>508</b> which begins at mini-slot <b>4</b> and continues through mini-slot <b>11</b> (M=8). In step <b>1204</b>, the scheduler process checks the transmitter node's transmit and receive schedule to determine whether any of the M mini-slots comprising the candidate time slot is already in use at the transmit node (for receiving or transmitting). The transmitter node's transmit and receive schedule can be stored in memory <b>450</b>. If any of the M mini-slots are currently in use, then the candidate time slot is not acceptable and the process continues to step <b>1206</b>. In step <b>1206</b>, the value of n is incremented and the step <b>1204</b> is repeated with a different set of M mini-slots. For convenience, the value of n can be incremented by 1. However, the invention is not limited in this regard. For example, the value of n could be incremented by M or any other value.

0075In step <b>1204</b>, if none of the M mini-slots are currently in use at the transmitter node, then the process continues on to step <b>1208</b>. In step <b>1208</b>, the scheduler process determines whether any of the M mini-slots are in use at the receiver node. Information concerning time slot usage at the receive node can be obtained from the neighbor time slot usage profile <b>428</b> which is stored in memory device <b>450</b>. If any of the time slots are currently in use at the receiver node, the process can return to step <b>1206</b> where the value of n is incremented to select a different set of M mini-slots. Alternatively, if the M mini-slots are not in use at the receiver node, then the process continues on to step <b>1210</b>.

0076In step <b>1210</b>, the scheduler process in the transmitter node determines whether the transmitter node's use of the M mini-slots associated will cause interference to neighboring nodes located in the transmit beam of the transmitter node (when pointed toward the receiver node). This process for mitigating interference is described below in more detail in relation to <figref idref="DRAWINGS">FIG. 14</figref>. If the scheduler process determines that use of the M mini-slots by the transmitter node will cause interference to neighboring nodes, then the process returns to step <b>1206</b> and an alternative set of mini-slots is selected for evaluation. Conversely, if the scheduler process determines that use of the M mini-slots by the transmitter node will not cause interference to neighboring nodes, then the process continues on to step <b>1212</b>.

0077In step <b>1212</b>, the candidate time slot comprised of the M mini-slots is added to a list of candidate time slots which can be used. Thereafter, in step <b>1214</b>, a determination is made as to whether the candidate transmit time slot list is complete. This determination can be based on any one of several considerations. For example, the list can be deemed complete when a predetermined number of candidate transmit time slots have been identified. Alternatively, the list can be complete when all possible candidate time slots have been considered.

0078Referring now to <figref idref="DRAWINGS">FIG. 14</figref>, there is provided a more detailed description of the process associated with step <b>1210</b> in <figref idref="DRAWINGS">FIG. 12</figref>. It may be recalled from the discussion regarding <figref idref="DRAWINGS">FIG. 12</figref>, that step <b>1210</b> generally involves a scheduler process at the transmitter node. The scheduler process is used to evaluate potential interference caused by the transmitting node's use of the M mini-slots associated with the candidate time slot. In particular, this scheduler process determines whether the transmissions by the transmitter node during the candidate time slot, using an antenna beam pointing toward the receiver node, will cause interference to other neighboring nodes that are also located in the transmit beam. As an aid in understanding, the process will be described with reference to <figref idref="DRAWINGS">FIGS. 6 and 7</figref> in which node <b>4042</b> is considered the transmitter node and node <b>4044</b> is considered to be the receiver node.

0079The process in <figref idref="DRAWINGS">FIG. 14</figref> begins with step <b>1402</b> in which the transmitter scheduler at the transmitter node determines a direction that it's transmit beam will be pointed for the purpose of communicating with the receiver node. In the context of <figref idref="DRAWINGS">FIGS. 6 and 7</figref>, this means that the node <b>4042</b> will determine which direction its antenna beam <b>602</b> should point for communications with node <b>4044</b>. Once the direction of the transmitter beam has been determined in step <b>1402</b>, the scheduler process at the transmitter node (<b>4042</b>) will determine in step <b>1404</b> whether there are any neighbor nodes that are contained within the transmit beam. If not, then it can be assumed that the transmitter node's use of the M minislots will not cause interference to any other nodes and the process will continue on to step <b>1412</b>.

0080Alternatively, if it is determined in step <b>1404</b> that there are neighbor nodes contained within the transmit beam, then the process continues on to step <b>1406</b>. For example, in <figref idref="DRAWINGS">FIG. 6</figref> nodes <b>4046</b>, <b>4047</b>, <b>4049</b> are in the transmit beam <b>602</b> (in addition to node <b>4044</b>). In step <b>1406</b> the scheduler process determines whether there are any neighbor nodes in the transmit beam that are scheduled to be receiving during the candidate transmit time slot as adjusted for propagation delay. This concept is illustrated in <figref idref="DRAWINGS">FIG. 7</figref>. In step <b>1406</b>, the transmitter scheduler would determine whether any of the nodes <b>4046</b>, <b>4047</b>, <b>4049</b> are scheduled to be receiving during time intervals <b>706</b>, <b>707</b>, <b>709</b>. If not, then it can be assumed that no interference will occur and the scheduler process continues on to step <b>1412</b>. Otherwise, the scheduler process goes on to step <b>1408</b>.

0081In step <b>1408</b>, a determination is made as to whether any of the receive beams of the neighbor nodes that will be receiving during the selected time interval as determined in step <b>1406</b> is pointing generally toward the transmitter during the candidate transmit time (adjusted for propagation delay). In the context of <figref idref="DRAWINGS">FIG. 7</figref>, this would mean determining whether the antenna beams of any of the nodes <b>4046</b>, <b>4047</b>, <b>4049</b> are pointing toward the transmitter node <b>4042</b>. In <figref idref="DRAWINGS">FIG. 6</figref>, it can be observed that antenna beam <b>606</b> of node <b>4046</b> is pointing toward the transmitter node <b>4042</b> during time interval <b>706</b>. In this example, the scheduler process would continue on to step <b>1410</b> and determine that the transmitter node's use of the M mini-slots associated with a particular candidate time slot will cause interference to the other nodes located in the transmit beam. Those skilled in the art will appreciate that the interference calculation in step <b>1408</b> may advantageously consider the side lobe characteristics of the transmitting and receiving antenna patterns and the distance between the transmitting and receiving nodes to determine if harmful interference could occur at a receiving node. The process would then continue on to step <b>1206</b> in <figref idref="DRAWINGS">FIG. 12</figref>. Alternatively, the scheduler process continues to step <b>1412</b> and determine that the transmitter node's use of the M mini-slots will not cause interference. From step <b>1412</b>, the process continues on to step <b>1212</b> where the candidate time slot is added to the candidate time slot list.

0082It may be recalled from <figref idref="DRAWINGS">FIG. 11</figref> that once a suitable list of candidate transmit time slots has been compiled in step <b>1102</b>, this list is communicated to the receiver in step <b>1104</b>. Thereafter, in step <b>1106</b> the scheduling process at the receiver determines which, if any, of the candidate time slots are acceptable. Step <b>1106</b> will now be described in further detail with reference to <figref idref="DRAWINGS">FIG. 13</figref>. The process can begin in step <b>1302</b> when the receiver scheduler receives the list of candidate transmit time slots at the receiver node. The process continues on to step <b>1304</b> in which the receiver scheduler selects the first candidate time slot on the list for evaluation.

0083The evaluation process begins in step <b>1306</b> with the receiver scheduler process at the receiver node determining whether the M mini-slots corresponding to the candidate transmit time slot are still idle and are therefore available. This step is somewhat redundant because a similar check is performed in step <b>1208</b>. However, it will be appreciated that the transmit and receive schedule at the receiver node will often contain scheduling information for the receiver mode that is more current than the corresponding information for the receiver node that is stored in at the transmitter node. Accordingly, step <b>1306</b> is a useful verification that the M mini-slots are still idle.

0084If the M mini-slots are determined to be no longer idle, then the process continues on to step <b>1312</b> where the receiver scheduler process determines whether there are any more candidate transmit time slots on the candidate transmit time slot list. Alternatively, in step <b>1306</b>, if the M mini-slots associated with a candidate time slot are in fact available, then the process continues on to step <b>1308</b>.

0085In step <b>1308</b>, the receiver scheduler process at the receiver node determines whether the receiver node will experience interference from network nodes other than the transmitter node. Step <b>1308</b> is described in greater detail in relation to <figref idref="DRAWINGS">FIG. 15</figref>. However, it should be understood that the receiver scheduler process in step <b>1308</b> determines whether the receiver node will experience interference from other neighboring nodes during the M mini-slots corresponding to the candidate transmit time slot (as adjusted in time to compensate for propagation delay). If, in step <b>1308</b>, the receiver scheduler process determines that no interference will result from neighboring nodes, then the process continues on to step <b>1108</b> in <figref idref="DRAWINGS">FIG. 11</figref>. In step <b>1108</b>, a message is sent to the transmitter node indicating that the candidate time slot is acceptable to the receiver node. Alternatively, if the receiver scheduler process determines that the receiver node will experience interference from other neighboring nodes, then the process continues on to step <b>1312</b>.

0086In step <b>1312</b>, the receiver scheduler process determines whether there are any other candidate time slots on the candidate time slot list. If so, then the receiver scheduler process continues on to step <b>1316</b> where the next candidate time slot is selected. Alternatively, if there are no more candidate time slots on the list, the receiver scheduler process continues on to step <b>1314</b> in which the receiver node notifies the transmitter node that none of the candidate time slots are acceptable. The receiver scheduler process then returns to step <b>1102</b> in <figref idref="DRAWINGS">FIG. 11</figref>, where a new list of candidate time slots is generated at the transmitter node.

0087Referring now to <figref idref="DRAWINGS">FIG. 15</figref>, the processes associated with step <b>1308</b> will now be described in greater detail. The process in <figref idref="DRAWINGS">FIG. 15</figref> begins with step <b>1502</b> in which the scheduler process at the receiver node determines a direction that it's receive beam will be pointed for the purpose of receiving communications from the transmitter node. In the context of <figref idref="DRAWINGS">FIGS. 8 and 9</figref>, this means that the node <b>4044</b> will determine which direction its receiver antenna beam <b>812</b> will need to point towards for communications with node <b>4042</b>. Once the direction of the receiver antenna beam <b>812</b> has been determined in step <b>1502</b>, the scheduler process at the receiver node (<b>4044</b>) will determine in step <b>1504</b> whether there are any neighbor nodes that are contained within the receiver antenna beam <b>812</b>.

0088If it is determined in step <b>1504</b> that there are no neighbor nodes contained within the receiver antenna beam <b>812</b>, then the process continues in step <b>1512</b>. In step <b>1512</b>, the scheduler process determines that the receiver node <b>4044</b> will not experience interference from other transmitting nodes during the time interval corresponding to the M mini-slots (as adjusted for propagation delay). Accordingly, the process will thereafter continue on to step <b>1108</b> in <figref idref="DRAWINGS">FIG. 11</figref>.

0089Alternatively, if it is determined in step <b>1504</b> that there are neighbor nodes contained within the receiver antenna beam <b>812</b>, then the process continues on to step <b>1506</b>. For example, in <figref idref="DRAWINGS">FIG. 8</figref> nodes <b>4041</b>, <b>4043</b>, <b>4045</b> are in the receiver antenna beam <b>812</b> (in addition to node <b>4042</b>). Accordingly, the process would continue on to step <b>1506</b> in the example shown in <figref idref="DRAWINGS">FIG. 8</figref>.

0090In step <b>1506</b> the scheduler process at the receiver node determines whether transmitted signals from any neighbor nodes in the receiver beam <b>812</b> can potentially be received at the receiver node <b>4044</b> during any of the mini-slots corresponding to the time interval <b>704</b>. This concept is illustrated in <figref idref="DRAWINGS">FIG. 9</figref>. Recall that time interval <b>704</b> is the period of time during which a transmission from transmitter node <b>4042</b> will actually be received at receiver node <b>4044</b> (assuming that the signal is transmitted from node <b>4042</b> during time slot <b>702</b>). Similarly, time intervals <b>901</b>, <b>903</b>, <b>905</b> represent those transmission time intervals for nodes <b>4041</b>, <b>4043</b>, <b>4045</b> that will result in signals actually being received at receiver node <b>4044</b> during time interval <b>704</b>.

0091In step <b>1506</b>, if none of the nodes <b>4041</b>, <b>4043</b>, <b>4045</b> are actually scheduled to be transmitting during the time periods <b>901</b>, <b>903</b>, <b>905</b>, then it can be concluded that no interference will be caused at the receiver node <b>4044</b> during time interval <b>704</b>. In that case, the transmit time slot <b>702</b> would be an acceptable time slot during which node <b>4042</b> can transmit to node <b>4044</b>, and the scheduler process continues on to step <b>1512</b>. Conversely, if any of the nodes <b>4041</b>, <b>4043</b>, <b>4045</b> are actually scheduled to be transmitting during the time periods <b>901</b>, <b>903</b>, <b>905</b>, then such transmissions can potentially cause interference at the receiver node <b>4044</b> during time interval <b>704</b>. In that case, the transmit time slot <b>702</b> may not be an acceptable time slot during which node <b>4042</b> can transmit to node <b>4044</b>. Accordingly, the scheduler process will continue on to step <b>1508</b>.

0092In step <b>1508</b>, a determination is made as to whether an antenna beam of any neighbor nodes that is actually pointed toward the receiver <b>4044</b> during a time interval when the receiver is expecting to receive signals from the transmitter node. In the context of <figref idref="DRAWINGS">FIG. 9</figref>, this would mean determining whether the antenna beams of any of the nodes <b>4041</b>, <b>4043</b>, <b>4045</b> are pointing toward the receiver node <b>4044</b> during time intervals <b>901</b>, <b>903</b>, <b>905</b>. If so, then the scheduler continues on to step <b>1510</b> where it determines that other transmitters will cause interference to the receiver if the transmitter node uses the M mini-slots associated with a candidate transmit time slot such as slot <b>702</b>. Those skilled in the art will appreciate that the interference calculation in step <b>1508</b> may advantageously consider the side lobe characteristics of the transmitting and receiving antenna patterns and the distance between the transmitting and receiving nodes to determine if harmful interference could occur at a receiving node. Following step <b>1510</b>, the scheduler process at the receiver node continues on to step <b>1312</b> in <figref idref="DRAWINGS">FIG. 13</figref>. In step <b>1312</b> the scheduler process checks to see if other candidate time slots are available and continues on as described above.

0093Referring additionally to <figref idref="DRAWINGS">FIGS. 16 and 17</figref>, another advantageous aspect is now described in which the nodes <b>404</b> operate and establish communications links therebetween based upon a TDMA implementation that does not use range dependent guard times, at Blocks <b>160</b>-<b>161</b>. More particularly, since the controller or control unit <b>408</b> knows its current position, as well as the position information of its neighboring nodes from the exchange of such information between nodes which is stored in the neighbor information table <b>420</b> (Block <b>165</b>′), the controller may therefore determine the range (and optionally angle) to the adjacent node it is communicating with, as described above. As a result, the controller <b>408</b> may therefore advantageously use this range (and, optionally, angle) information to schedule time slots to offset a link delay in a received signal from the adjacent MANET node, without the need for a built in guard time, at Block <b>163</b>, thus concluding the method in <figref idref="DRAWINGS">FIG. 16</figref> (Block <b>164</b>).

0094That is, since the controller <b>408</b> advantageously implements the above-described distributed TDMA scheduling operations with variable-length time slot (i.e., mini-slot) allocation, the range effects due to link delay may therefore be removed, as will be appreciated by those skilled in the art. As noted above, huesistics may advantageously be used to provide an efficient distributed schedule that includes both range and angle (for directional antenna isolation) in the calculations, which can advantageously reduce control overhead while at the same time scheduling time slots to reduce a likelihood of interference, at Block <b>166</b>′, as discussed further above. It should be noted that in this TDMA implementation (and the following discussed with reference to <figref idref="DRAWINGS">FIGS. 18-19</figref>), an omni-directional link may be used in some applications as well as directional links.

0095Moreover, either receiver-oriented or transmitter-oriented scheduling of the variable length time slots may be used. Additionally, flexibility of time slot assignment is also provided. For example, if the required capacity can be delivered by eight minislots, there may be no string of eight contiguous minislots that meet the interference criteria. However, it may be possible for two groups of four minislots or four groups of two minislots to provide the capacity and meet the interference criteria, which may advantageously be done in accordance with the invention. Generally speaking, as link bit rate changes with range or propagation or interference, it is more efficient to provide capacity using variable time slots than with fixed time slots, although fixed time slots may also be used in some embodiments.

0096Turning now to <figref idref="DRAWINGS">FIGS. 18-19</figref>, another advantageous aspect is described in which the TDMA implementation uses a repeating scheduling of a plurality of temporally spaced-apart time slot units within a control epoch to thereby advantageously reduce a latency of communication (Block <b>167</b>′). More particularly, the above-noted variable time slot control implementation may advantageously be used to adjust the TDMA schedule to jointly optimize the capacity and latency assigned to a connection. <figref idref="DRAWINGS">FIG. 19</figref> shows the timing of an exemplary TDMA format. In the illustrated example, each control epoch includes Nm=1000 mini-slots, as shown. In a fixed time slot length TDMA implementation, all time slots include a same number of slots or mini-slots.

0097In a variable length TDMA implementation, the time slots can vary in length from Nmin to Nmax mini-slots. Moreover, time slots can also start in any mini-slot. This is shown in <figref idref="DRAWINGS">FIG. 19</figref> by a time slot <b>170</b> that includes six mini-slots (i.e., mini-slots <b>3</b>-<b>8</b>), and other time slots <b>171</b><i>a</i>, <b>171</b><i>b </i>which include three mini-slots each (i.e., <b>3</b>-<b>5</b> and <b>503</b>-<b>505</b>, respectively). If the TDMA schedule is unchanged during a sequence of control epochs, the time slot assignments repeat during every control epoch.

0098Consider a variable length time slot TDMA system. For a fixed schedule, during the time the schedule is executed, the capacity assigned to a connection is given by:

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>=</mo><mfrac><mrow><msub><mi>N</mi><mi>i</mi></msub><mo></mo><msub><mi>T</mi><mrow><mi>m</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>s</mi></mrow></msub><mo></mo><msub><mi>R</mi><mi>i</mi></msub></mrow><msub><mi>T</mi><mi>c</mi></msub></mfrac></mrow><mo>,</mo></mrow></math></maths><img file="US2009034491A1_D0001.tif" />

0000where C_iis the instantaneous capacity of the connection, N_iis the number of mini-slots assigned to the time slot, R_iis the current over-the-air link rate, T_msis the time duration of a mini-slot, and T_cis the time duration of a control epoch. For a specific numerical example, consider a variable length time slot TDMA system where the mini-slot time duration T_msis 0.1 msec, the control epoch T_cis 100 msec, and the instantaneous link rate R_iis 10 mbps. If a connection is assigned a time slot including one mini-slot, then the connection has a capacity of 10 kbps.

0099Consider the case where the scheduler is required to assign 60 kbps capacity to a connection. The time slot <b>170</b> in begins at mini-slot <b>3</b> and ends after mini-slot <b>8</b>. Based on the above calculation, this provides 60 kbps of capacity. The worst case latency occurs when a packet arrives from the router in mini-slot <b>3</b> (assuming that the radio is unable to send anything in the time slot that has not been in the transmit buffer prior to mini-slot <b>3</b>), and has to wait an entire control epoch before it can be transmitted. For a uniform random distribution of arrival times, the average wait time is then one half the control epoch or 50 msec.

0100By comparison, use of the temporally spaced-apart time slot units <b>171</b><i>a</i>, <b>171</b><i>b </i>provides an alternate scheduling approach that provides the required 60 kbps capacity to the connection, but also advantageously reduces latency. More particularly, the pair of time slot units <b>171</b><i>a</i>, <b>171</b><i>b </i>provides a total of six mini-slots to give the requisite 60 kbps capacity. However, the worst case waiting time is reduced to one half of the control epoch length, since there are two time slots <b>171</b><i>a</i>, <b>171</b><i>b </i>temporally equally spaced-apart in each epoch. Thus, a packet arriving in mini-slot <b>3</b> needs only to wait until the mini-slot <b>503</b> to begin transmission. So, for a uniform distribution of arrival times, the average waiting time in this case is one quarter the control epoch length. It will be appreciated that in some embodiments this approach may be implanted using regular time slots (i.e., as opposed to mini-slots), and that other numbers may also be used.

0101For example, the latency may be further reduced by spacing three transmissions of two mini-slots each in the control epoch, or six transmissions of one mini-slot each in the control epoch. However, it will be appreciated that the latency savings achieved thereby are bounded by the overhead associated with such a transmission. That is, at some point this overhead will reduce the efficiency to a degree that the marginal gain in latency will not be desirable, so it is typically desirable to balance the latency and overhead based upon the given implementation, as will be appreciated by those skilled in the art. Also, when scheduling one or more time slots using this approach, the interference calculations and current schedule will affect the placement of the time slots. Interference is preferably considered when determining the scheduling of the time slots in addition to the capacity and latency.

0102Scheduling the one or more timeslots using a fixed separation rule for timeslot distribution through the epoch may result in poor interference performance, since with a fixed separation rule, interference between two or more nodes in one timeslot may also result in interference between the same nodes in all timeslots. A fully random separation process, on the other hand, may not assure that the timeslots on a link are well distributed throughout the epoch. Thus, while either approach could be used in certain embodiments, another approach for distribution may advantageously both distribute the timeslots through the epoch and also vary the spacing between the timeslots used on any one link.

0103An exemplary algorithm for the separation rule that provides distributed timeslots is to divide the epoch into a number of sub-divisions. These sub-divisions can then be used to achieve the desired distribution and variable separation using the following multi-step rule. <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0104">1. Assign the first timeslot to a link based upon interference calculations as discussed above.</li><li id="ul0002-0002" num="0105">2. Preferentially assign the second timeslot to the same link in the frame spaced one-half epoch away from the first frame. The exact timeslot (or set of mini-slots) is defined using the interference avoidance rules as described above with the search beginning in the preferred frame.</li><li id="ul0002-0003" num="0106">3. Add other timeslots to the same link in a similar manner where the preferred frame (i.e., the frame where the search for a suitable timeslot is to begin) is a frame that is equally spaced from all of the frames where the link already has a timeslot assigned.</li><li id="ul0002-0004" num="0107">4. In the unlikely event that all frames have a timeslot for a particular link and even more timeslots are required, add the next timeslot preferentially to the first frame where a timeslot was assigned and continue the process as above.</li></ul></li></ul>

0108An alternate embodiment for the distributed timeslot assignment algorithm would be to begin the search for the next suitable timeslot on a link at a mini-slot defined by adding an integer number of mini-slots to the last mini-slot in the previously assigned timeslot, where the integer is defined by adding a fixed separation equal to one-half the average distance between the other slots assigned to the same link to a random number of minislots. The average of this random number should be realatively small. For example, in one embodiment this average value is set to two times the number of mini-slots used in a timeslot. Other choices for the distribution algorithm will occur to those skilled in the art.

0109An exemplary scheme for variable length time slots will now be described. Here a metric is used that is based upon an average utilization of the transmit time slots allocated on a connection, namely Tx_Time slot_Utilization=a moving average of the utilization of the multiple variable length time slots allocated on a connection. One can set parameters for minimum time slot length, Min_TS_Len and maximum time slot length, Max_TS_Len, and assume upper and lower thresholds are set for the metric, Tx_Time slot_Utilization, which are used for determining whether to add or subtract capacity on that connection. These thresholds are Tx_Util_upper and Tx_Util_lower. Capacity will be added or released to control the utilization and keep it within the range of these upper and lower thresholds.

0110The amount of capacity that will be released or added on one operation will be determined as a change in utilization by a fractional adjustment of the current capacity allocation using

0000<br /><i>Kfrac=Ku</i>*(<i>Tx</i>_—<i>Util</i>_upper−<i>Tx</i>_—<i>Util</i>_lower),

0000where Ku is in the range of 0.1 to 0.5. This will make the adjustment a small enough amount so that it will not result in limit cycle behavior. The resulting change in the utilization will be to move utilization from one side of a threshold to, at worst, the other side of that threshold, but not to the other threshold. Denoting the current capacity allocation (i.e., the amount of time in the epoch allocated to this transmit connection) as Cur_Tx_Time_per_Epoch, then the increment of additional time added or released on one operation will be

0000<br />New_Time_Increment=<i>Kfrac*Cur</i>_—<i>Tx</i>_Time_per_—<i>Epoch. </i>

0000Thus, if the utilization is too high, and additional capacity is needed, the new time allocation per epoch is

0000<br />New_—<i>Cur</i>_—<i>Tx</i>_Time_—<i>per</i>_—<i>Epoch=Cur</i>_—<i>Tx</i>_Time_—<i>per</i>_—<i>Epoch</i>+New_Time_Increment.

0000Similarly, we subtract the New_Time_Increment if we need to release capacity. This can be summarized by the following algorithm: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0111">If Tx_Time slot_Utilization<Tx_Util_lower Release New_Time_Increment of capacity</li><li id="ul0004-0002" num="0112">Else if Tx_Time slot_Utilization>Tx_Util_upper Add New_Time_Increment of capacity</li><li id="ul0004-0003" num="0113">Else do nothing.</li></ul></li></ul>

0114If an increment of capacity is added or released, the controller <b>408</b> may wait a small number of epochs before taking further action to allow the estimate of Tx_Time slot_Utilization to settle on a new value. These algorithms may be applied to TDMA formats that use mini-slots as in <figref idref="DRAWINGS">FIG. 19</figref>, or formats that use variable length time slots that are continuously variable. In the cases of mini-slots, the New_Time_Increment may be rounded to the nearest mini-slot.

0115If the utilization evaluation indicates that capacity should be released on a transmit connection, then the following procedures my be used. Capacity can be released without negotiating with the receiving node or evaluating if the release causes interference. The capacity allocation is denoted by Cur_Tx_Time_per_Epoch, which includes a set of k time slots with lengths T<b>1</b>, T<b>2</b>, . . . , Tk. Each of these time slots preferably has a length that is not less than Min_TS_Len. The capacity is released by reducing the allocation to the set of time slots by an amount equal to the New_Time_Increment. Thus, the new values of the time slot allocations will satisfy

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></munderover><mo></mo><mi>Ti</mi></mrow><mo>=</mo><mrow><mrow><mi>Cur_Tx</mi><mo></mo><mi>_Time</mi><mo></mo><mi>_per</mi><mo></mo><mi>_Epoch</mi></mrow><mo>-</mo><mrow><mi>New_Time</mi><mo></mo><mrow><mi>_Increment</mi><mo>.</mo></mrow></mrow></mrow></mrow></math></maths><img file="US2009034491A1_D0002.tif" />

0116The priorities used for accomplishing this reduction in time allocation per epoch can have a number of variations.

0117One exemplary approach is the following: <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0000"><ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0118">(1) The transmit node determines how to modify the time slot lengths. The highest priority is to reduce the individual time slot allocations while keeping all of them greater than the Min_TS_Len. A time slot may be reduced in length either by eliminating some of the time from the start of the frame, the end of the frame or both.</li><li id="ul0006-0002" num="0119">(2) If the time slots are already so short that the capacity cannot be reduced enough by shortening the time slots, then a time slot is preferably released. The highest priority time slot to release is the minimum length time slot which has length greater than Min_TS_Len.</li><li id="ul0006-0003" num="0120">(3) If no time slot satisfying (2) can be found, then the maximum length time slot is released.</li></ul></li></ul>

0121After capacity is released, the transmit node notifies the receiving node via an in-band control message of the details of the capacity release (time slot allocation changes). When the utilization evaluation indicates that capacity should be added to a transmit connection, the resulting change in capacity allocation is done while evaluating if any interference constraints are violated, and the change in allocation should be agreed to by the receiving node. Once the need to increase capacity is determined, then the value of New_Time_Increment is calculated. Then the new allocations to time slot lengths should satisfy the following:

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></munderover><mo></mo><mi>Ti</mi></mrow><mo>=</mo><mrow><mrow><mi>Cur_Tx</mi><mo></mo><mi>_Time</mi><mo></mo><mi>_per</mi><mo></mo><mi>_Epoch</mi></mrow><mo>+</mo><mrow><mi>New_Time</mi><mo></mo><mi>_Increment</mi></mrow></mrow></mrow></math></maths><img file="US2009034491A1_D0003.tif" />

0122Several approaches could be used in lengthening the time slot allocations or adding new time slots. One example is as follows: <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0000"><ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0123">(1) The transmit node evaluates the interference constraint impact of adding additional time at either the start or end of each time slot, or both, while keeping the new time slot length to no more than Max_TS_Len. The value of New_Time_Increment is allocated across as many time slots as possible and as equally as possible.</li><li id="ul0008-0002" num="0124">(2) If the currently allocated time slots are already so long that New_Time_Increment cannot be fully allocated, then a new time slot is added with this length. Interference constraints should be evaluated to determine where in the epoch this time slot should be placed.</li><li id="ul0008-0003" num="0125">(3) If no time slot candidate as large as needed in (2) can be found, then a candidate time slot may be built from a list of shorter time slots. In addition, existing time slots may be extended where possible.</li></ul></li></ul>

0126The list of time slot extensions and new candidate time slots are candidates to be offered to the receiving node in an in-band control Request message. The receiving node may also evaluate the interference constraints from its perspective of each of these candidates. Once this is done, it will select from the candidates those that also do not violate interference constraints in order to select a group that results in achieving the addition of the amount, New_Time_Increment, of time allocation per epoch. The list of selected changes are sent back to the transmit node in a Reply message. Once the Reply message is received, the transmit node may start using these changed time slot allocations.

0127Additional features of the invention may be found in a co-pending patent application filed concurrently herewith and assigned to the Assignee of the present invention entitled MOBILE AD-HOC NETWORK PROVIDING COMMUNICATION LATENCY REDUCTION FEATURES AND RELATED METHODS, attorney docket number GCSD-1997 (61668), the entire disclosure of which is hereby incorporated herein in its entirety by reference.

0128Many modifications and other embodiments of the invention will come to the mind of one skilled in the art having the benefit of the teachings presented in the foregoing descriptions and the associated drawings. Therefore, it is understood that the invention is not to be limited to the specific embodiments disclosed, and that modifications and embodiments are intended to be included within the scope of the appended claims.