Methods and systems for cooperative transmission in multi-hop ad-hoc networks

CROSS REFERENCE TO RELATED APPLICATIONS

0001This application claims priority of U.S. Provisional Application 60/504,845 filed on Sep. 22, 2003, which is herein incorporated by reference.

STATEMENT OF GOVERNMENT INTEREST

0002This invention was made partially with U.S. Government support from the National Science Foundation under grant CCR-0227676 and ONR Contract N00014-00-1-0564. The U.S. Government has certain rights in the invention.

BACKGROUND OF THE INVENTION

0003This invention relates generally to wireless networks, and, more particularly, to methods and systems for cooperative transmission in multi-hop ad-hoc networks.

0004An ad-hoc network architecture is a network that can be deployed rapidly and without relying on preexisting fixed network infrastructure. Personal communications and mobile computing require a wireless network infrastructure that is fast deployable, possibly multi-hop, and such an infrastructure is provided by multi-hop ad-hoc networks.

0005Since the first appearance of wireless ad hoc networks as the DARPA packet radio networks in the 1970s, wireless ad hoc networks have been the subject of research and development and have been considered for a number of applications. Proposed applications of wireless ad hoc networks include, but are not limited to: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0006"> tactical operation—for fast establishment of communication infrastructure during force deployment in unknown and hostile terrain; </li><li id="ul0002-0002" num="0007"> rescue missions—for communication in areas without adequate wireless coverage; </li><li id="ul0002-0003" num="0008"> national security—for communication in times of national crisis, where the existing communication infrastructure is non-operational due to a natural disaster or a global war; </li><li id="ul0002-0004" num="0009"> law enforcement—for fast establishment of communication infrastructure during law enforcement operations; </li><li id="ul0002-0005" num="0010"> commercial use—for setting up communication in exhibitions, conferences, or sale presentations; </li><li id="ul0002-0006" num="0011"> education—for operation of wall-free (virtual) classrooms; and </li><li id="ul0002-0007" num="0012"> sensor networks—for communication between intelligent sensors mounted on mobile platforms. </li></ul></li></ul>

0013However, multi-hop network protocols are presently designed using the paradigm of packet Networks and of point to point communications. Messages are delivered by going through a series of intermediate nodes through point to point links forming a routing path. In many applications of ad-hoc networks the medium is broadcast; therefore to attain point to point communications it is necessary to perform a Multiple Access protocol and resolve the contention in using the medium. Once the access is granted to a source and destination pair, the Physical Layer functions (source/channel coding) that pertain to each link are done locally. There is a need for a cooperative form of transmission performed by a set of asynchronous transceivers operating as a distributed joint communication system.

0014The nodes in ad-hoc networks are generally designed with low power transmitters whose power often not sufficient for communication towards distant receivers. This problem is often referred to as the reach back problem in military applications and could have an important role in more general sensor network applications.

0015The trademark of the reach-back problem is that the information from an arbitrary network node cannot be forwarded to a receiver that does not have a relay node in its vicinity without quickly draining its energy resources. The reach back point is “disconnected” since there is no point to point link that can be established towards it. Surprisingly, even though it appears to be a very concrete problem, the reach back problem has not received a critical mass of attention. There is a need for methods and systems that provide means for communicating with distant receivers, that is, solutions to the reach back problem.

SUMMARY OF THE INVENTION

0016Methods and systems that enable a cooperative form of transmission performed by a set of asynchronous transceivers operating as a distributed joint communication system are disclosed.

0017In an embodiment of the method of this invention, information is transmitted from one or more predetermined nodes (the source nodes) in the network. The information is received at the other nodes (the receiving nodes) in the network. For every information symbol/codeword each of the receiving nodes receives an accumulation of signals from nodes transmitting an earlier stage. At each of the receiving nodes a predetermined criterion is utilized to decide whether to retransmit the received information. If retransmission is indicated, the signal modulating the information symbol is retransmitted from the receiving nodes and delivered to an increasing number of downstream nodes. The accumulation of signals from this chain of retransmissions forms a network signature waveform that embeds the information data as well as the transmission power of multiple sources. This is equivalent to a distributed modulation system, where multiple points communicate to various destinations simultaneously.

0018In the system (network) of this invention, the transmission of the information in the network is led by one or more predetermined source nodes in the network. All the other nodes form multiple stages of relays to either flood the network with the information from the source, or just to pass the information to a remote receiver. The receiving nodes have a choice of whether to relay or not, depending on a predetermined criterion at that node.

0019The receiving nodes have the choice of retransmitting the received symbol or to stay silent. In one embodiment, in the regenerative scheme, only nodes whose maximum pair-wise symbol error probability (not considering error propagation) is below a pre-selected upper-bound actively reply. In another embodiment, only nodes whose SNR is above a fixed threshold actively reply.

0020In one embodiment, the transmitted signal is linearly modulated. In another embodiment, the modulation of the transmitted signal produces orthogonal signals. In a further embodiment, a modulation method of this invention, Leader Position Modulation, is used. The optimum maximum likelihood (ML) receiver of this invention is adapted to the transmission environment of this invention.

0021An embodiment of the method and system of this invention enables communicating with distance receivers (that is, presents a solution to the reach back problem).

0022An embodiment of the method of this invention is a physical layer flooding algorithm, which results in a network, that implements that embodiment of the method, which does not require the routing and multiple access overheads. (“Physical layer” is used herein in the same manner as used in computer networks and in the ISO model. See, for example, A. Tannenbaum, Computer Networks, ISBN 0-13-165183-8, 1981, pp. 10-16.)

0023In embodiments of this invention that adopt incoherent schemes such as OOK or FSK, the receivers are simply energy detectors and only symbol synchronization is required, but not training.

0024For a better understanding of the present invention, together with other and further objects thereof, reference is made to the accompanying drawings and detailed description, and its scope will be pointed out in the appended claims.

BRIEF DESCRIPTION OF THE DRAWINGS

0025<figref idref="DRAWINGS">FIG. 1</figref> is a flowchart representation of one embodiment of the method of this invention;

0026<figref idref="DRAWINGS">FIG. 2</figref><i>a </i>is a graphical schematic representation of a four node embodiment of a system of this invention;

0027<figref idref="DRAWINGS">FIG. 2</figref><i>b </i>is a schematic block diagram representation of an embodiment of a leader node of this invention;

0028<figref idref="DRAWINGS">FIG. 2</figref><i>c </i>is a schematic block diagram representation of an embodiment of a receiving node of this invention;

0029<figref idref="DRAWINGS">FIG. 2</figref><i>d </i>is a schematic block diagram representation of an embodiment of a component of a receiving node of this invention;

0030<figref idref="DRAWINGS">FIG. 2</figref><i>e </i>is a schematic block diagram representation of another embodiment of a component of a receiving node of this invention;

0031<figref idref="DRAWINGS">FIG. 3</figref> is a graphical schematic representation of the signal received at each receiving node of the system shown in <figref idref="DRAWINGS">FIG. 2</figref><i>a; </i>

0032<figref idref="DRAWINGS">FIG. 4</figref> is a graphical schematic representation of the signal received at a receiving node of the system of this invention;

0033<figref idref="DRAWINGS">FIG. 5</figref> is a graphical schematic representation of the signal received at each receiving node of a regenerative embodiment of the system shown in <figref idref="DRAWINGS">FIG. 2</figref><i>a; </i>

0034<figref idref="DRAWINGS">FIG. 6</figref> is a graphical schematic representation of an embodiment of a system of this invention including a remote receiver; and,

0035<figref idref="DRAWINGS">FIG. 7</figref> is a graphical representation of results for a network of this invention.

DETAILED DESCRIPTION OF THE INVENTION

0036Methods and systems that enable a cooperative form of transmission performed by a set of asynchronous transceivers operating as a distributed joint communication system are disclosed hereinbelow.

0037<figref idref="DRAWINGS">FIG. 1</figref> is a flowchart representation of one embodiment of the method of this invention. Referring to <figref idref="DRAWINGS">FIG. 1</figref>, information is transmitted from one or more predetermined nodes (the source nodes) in the network (step <b>20</b>, <figref idref="DRAWINGS">FIG. 1</figref>). The information is received at the other nodes (the receiving nodes) in the network (step <b>30</b>, <figref idref="DRAWINGS">FIG. 1</figref>). Each of the receiving nodes receives an accumulation of signals from nodes transmitting an earlier stage. At each of the receiving nodes a predetermined criterion is utilized to decide whether to retransmit the received information (step <b>40</b>, <figref idref="DRAWINGS">FIG. 1</figref>). If retransmission is indicated, the information is retransmitted from the receiving nodes (step <b>50</b>, <figref idref="DRAWINGS">FIG. 1</figref>). The transmission method of this invention is hereinafter also called an Opportunistic Large Array (OLA) method.

0038In one embodiment of the method of this invention the step of determining whether to retransmit comprises the steps of determining a pair wise symbol error probability for received information at each one of the receiving nodes, and determining at each one of the receiving nodes whether the pair wise symbol probability satisfies a predetermined criterion.

0039In one embodiment, the receiving nodes (also called Opportunistic Large Array—OLA-nodes) have the choice of transmitting the received (also referred to as detected) symbol or to stay silent. In one embodiment, hereinafter referred to as the regenerative scheme, the predetermined retransmission criterion applied at each of the receiving nodes includes re-transmitting only from nodes whose pair wise symbol error probability (in one embodiment, but not a limiting condition, not considering error propagation) is below a pre-selected upper-bound actively reply.

0040In another embodiment of the method of this invention the step of determining whether to retransmit comprises the steps of determining a signal to noise ratio for received information at each one of the receiving nodes, and determining at each one of the receiving nodes whether the signal to noise ratio satisfies a predetermined criterion. In the above described embodiment, hereinafter referred to as the non-regenerative scheme, only nodes whose SNR is above a fixed threshold actively reply.

0041A graphical schematic representation of a four node embodiment <b>10</b> of a system of this invention is shown in <figref idref="DRAWINGS">FIG. 2</figref><i>a</i>. Node <b>1</b> is selected as a leader (source, also referred to as transmitting) node, and nodes <b>2</b>, <b>3</b>, and <b>4</b> are the receiving nodes. <figref idref="DRAWINGS">FIG. 3</figref> depicts a graphical schematic representation of the aggregated signals received at each receiving node, nodes <b>2</b>, <b>3</b>, and <b>4</b> of the system shown in <figref idref="DRAWINGS">FIG. 2</figref><i>a</i>. Each node receives an accumulation of signals from nodes transmitting in the earlier stage, and retransmits when the predetermined retransmission criterion is achieved. The signal is received using an adaptive receiver. A generalized embodiment of the system of this invention includes a number of nodes. One of the nodes is the source (transmitting) node <b>22</b>, shown schematically in <figref idref="DRAWINGS">FIG. 2</figref><i>b</i>, and includes a transmitter <b>25</b> (a transmitter as used herein may include a transmitting component such as, but not limited to, an antenna). The remaining nodes are receiving nodes and each receiving node <b>32</b>, one of which is shown schematically in <figref idref="DRAWINGS">FIG. 2</figref><i>c</i>, includes a receiver <b>35</b> (a receiver as used herein may include a receiving component such as, but not limited to, an antenna), means for applying a predetermined retransmission criterion (such as computing means) <b>45</b>, and a transmitter <b>55</b>. In one embodiment the receiver, means <b>45</b> for applying a predetermined retransmission criterion, and the transmitter could be integrated in one system, hereinafter referred to as a transceiver.

0042In one embodiment, each node in the OLA network is assumed to have identical transmission resources, therefore, any node has the ability of assuming the role of a leader. The leader can be chosen by any predetermined criterion including, but not limited to, being the cluster-heads in clustering algorithms, or simply some node that has information to send.

0043One embodiment <b>100</b> of the means <b>45</b> for applying a predetermined retransmission criterion is shown in <figref idref="DRAWINGS">FIG. 2</figref><i>d</i>. Referring to <figref idref="DRAWINGS">FIG. 2</figref><i>d</i>, a received signal <b>110</b> is provided, in digital form, from the receiver <b>35</b> to a processor <b>120</b>. The processor <b>120</b> can comprise one or many processing units. A computer usable medium <b>130</b> that has computer readable code embodied therein for applying a predetermined criterion to decide whether to retransmit the received information. The computer readable code causes the processor <b>120</b> to determine whether to retransmit the received information and to generate an enabling or disabling signal <b>140</b> which is provided to the transmitter <b>55</b>. The processor <b>120</b> and the computer usable medium <b>130</b> are operatively connected through interconnection means <b>135</b> (such as, but not limited to, a bus). It should be noted that equivalently, the same functions shown in <figref idref="DRAWINGS">FIG. 2</figref><i>d </i>could be accomplished by application specific or field programmable components.

0044Another embodiment <b>150</b> of the means <b>45</b> for applying a predetermined retransmission criterion is shown in <figref idref="DRAWINGS">FIG. 2</figref><i>e</i>. Referring to <figref idref="DRAWINGS">FIG. 2</figref><i>e</i>, a signal <b>155</b>, indicative of a predetermined quantity and determined from the received signal <b>110</b>, is provided from the receiver <b>35</b> to a comparator <b>160</b>. A signal <b>165</b>, indicative of a predetermined criterion is also provided to a comparator <b>160</b>. The comparator <b>160</b> generates an enabling or disabling signal <b>170</b> which is provided to the transmitter <b>55</b>.

0045In an embodiment of the network of N nodes of this invention transmitting over a shared medium, each node is part of a multiple stage relay of single source transmitting towards a remote receiver whose position is unknown to all the nodes. If no node in the network is powerful enough to communicate reliably with the remote receiver the problem is denoted as the reach-back problem. Coordination among nodes in a large network is an extremely difficult task, therefore, a cooperative transmission mechanism is designed for which cooperation is obtained in a distributed fashion.

0046In one embodiment of the systems and methods of this invention, the leader transmits a pulse with complex envelope p_m(t) out of an M-ary set of waveforms. The resulting signal at the ith receiver is <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><msub><mi>τ</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><msub><mi>a</mi><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>+</mo><mrow><msub><mi>n</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mrow><msub><mi>s</mi><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mrow><msub><mi>A</mi><mrow><mi>i</mi><mo>,</mo><mi>n</mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><msub><mi>p</mi><mi>m</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><mrow><msub><mi>τ</mi><mrow><mi>i</mi><mo>,</mo><mi>n</mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><mi>M</mi><mo>-</mo><mn>1</mn></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> where n_i(t) is the ith receiver Additive White Gaussian Noise (AWGN) with variance N₀; <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0047"> τ_i,n(t) is the delay of the link between the ith and the nth node, including the asynchronous of the beginning of transmission for each node n; and Ai,n(t) is the product of a complex fading coefficient ω_i,n(t) times the transmit power P_ttimes the channel average gain, e.g. a (1+d_i;n)^−α^{<sub2>i,n </sub2>}(lognormal fading) where d_i;nis the distance and α_i,nthe decay constant between the ith and nth node. </li></ul>

0048In one embodiment of the system of this invention A_i;n(t) and τ_i;n(t) are constant over multiple symbol durations T_s, therefore, the time dependence for both of them is omitted in later derivations. Physically, the nodes are quasistationary for a time much greater than T_s; the delays are τ_i;1&lt;τ_i;2&lt; . . . ≦τ_i;N, where the minimum delay τ_i;1corresponds to the leader. To avoid Inter Symbol Interference (ISI) the upper-bound for the effective symbol rate is R_s=1/T_s≦1/Δt, where Δt is the maximum delay spread of S_i;m(t) for all i.

0049The delay spread for node i is defined as <br />σ_τ_{<sub2>i</sub2>}={square root}{square root over (∫_−∞^∞(<i>t</i>−τ)}_i)²<i>·|s</i>_i,m(<i>t</i>)|²<i>dt</i>  (3) <ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0000"><ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0050"> where the average delay is <br />{overscore (τ)}_i=∫_−∞^∞<i>t·|s</i>_i,m(<i>t</i>)|²<i>dt </i></li><li id="ul0005-0002" num="0051"> and, thus, Δt=max_iσ_τ_{<sub2>i</sub2>}. </li></ul></li></ul>

0052Echoes that come from farther away are strongly attenuated (by ≈d^−α), therefore, the echoes received at node i are non-negligible only for those coming from nodes within a certain distance Δd which essentially depends on the transmit power and path loss. Hence, Rs can be increased by lowering the transmit power, capitalizing on spatial bandwidth reuse. In the reach back problem, however, the delay spread is Δτ≈sup_i[τ_i,N−τ_i,1] because the receiver is roughly at the same distance from all nodes.

0053In the above described embodiment of the system of this invention, Ts is fixed for all nodes to c₁Δτ where c₁is a constant taken to satisfy the ISI constraint. This embodiment guarantees that no ambiguity will occur at the nodes in timing their responses. The transmission activity of the node is solely dependent on the signal that the node receives. Based on the evolution of s_i,m(t) two phases can be distinguished: 1) the earlier receive phase, when the upstream waves of signals approach the node and, 2) the period after the firing instant, which is hereinafter called the rest phase, where the node hears the echoes of the downstream wave of signals fading away (for the regenerative case, the firing instant occurs shortly after the time when the node has accumulated enough energy to detect the signal). The switching between the two modes can be viewed as a very elementary form of Time-Division Duplex (TDD) (see <figref idref="DRAWINGS">FIG. 4</figref>).

0054In the above described embodiment of the system of this invention, the leader (and also the nodes in the regenerative case) transmit pulses with complex envelope p_m(t) having limited double-sided bandwidth W and approximately duration T_p. By sampling at the Nyquist rate, Np=T_pW is the approximate length of the sequence {p_m(k/W)} of samples.

0055Multi-path propagation can be simply included in the above embodiment by increasing the number of terms in the summation in Equation (2). If the propagation of errors and noise that occurs in the case of regenerative and non-regenerative repeaters respectively are neglected, as in Equation (2), the embodiment of the system of this invention is equivalent to a multi-path channel, created by a set of active scatterers.

0056In the regenerative case, the response of the embodiment of the system of this invention is: <maths id="MATH-US-00002" num="2"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>g</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>τ</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><msup><mi>N</mi><mi>′</mi></msup></munderover><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><msub><mi>A</mi><mrow><mi>i</mi><mo>,</mo><mi>n</mi></mrow></msub><mo>⁢</mo><mrow><mrow><mi>δ</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>τ</mi><mo>-</mo><msub><mi>τ</mi><mrow><mi>i</mi><mo>,</mo><mi>n</mi></mrow></msub></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>4</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0057The non-regenerative case is more complex due to the feedback effect that implies that not one but several signal contributions are scattered by each source. The received signal is: <maths id="MATH-US-00003" num="3"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>g</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>τ</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><msup><mi>n</mi><mi>′</mi></msup><mo>=</mo><mn>1</mn></mrow><msup><mi>N</mi><mi>′</mi></msup></munderover><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><msub><mi>A</mi><mrow><mi>i</mi><mo>,</mo><msup><mi>n</mi><mi>′</mi></msup></mrow></msub><mo>⁢</mo><mrow><mrow><mi>δ</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>τ</mi><mrow><mi>i</mi><mo>,</mo><msup><mi>n</mi><mi>′</mi></msup></mrow></msub></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>5</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0058For every possible path in the network, there is a contribution to the summation in Equation (5) that has an amplitude equal to the product of all the path link gains and a delay equal to the sum of all the path delays. Theoretically, the number of reflections N′→∞ because the signals and their amplified versions keep cycling in the network and adding up. Practically, the amplifiers are physically limited to emit no more power than the saturation level of the amplifiers at the nodes and the delay spread of the response is limited. If properly controlled, the contributions will keep adding up and then opportunistically serve the purpose of enhancing the signal. Hence, the key for the non-regenerative design is to control the noise that accompanies the useful signal (as further described hereinbelow).

0059In both regenerative and non-regenerative cases the received signal can be rewritten as (* denotes the convolution): <br /><i>r</i>_i(<i>t</i>=<i>g</i>_i(<i>t</i>)*<i>p</i>_m(<i>t</i>)+<i>n</i>_i(<i>t</i>),  (6) <br /> where g_i(t) is the network impulse response, analogous to that of a multi-path channel. Equation (6) is illustrative of this invention, which allows the nodes operate as regenerative and non-regenerative repeaters and avoid any complex coordination procedure to forward their signals at the network layer and share the bandwidth at the Medium Access Control (MAC) layer. Also, no channel state information is used. The information flow is carried forward by using receivers that are capable to track the unknown network response g_i(t), or directly the signature waveforms s_i;m(t)=g_i(t)*p_m(t). Equation (6) can be expressed in matrix form where the convolution is expressed as a Toeplitz convolution matrix, <br />{G_i}_k,n={g_i}_k-n, <ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0000"><ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0060"> n=0, . . . , N_p−1; </li><li id="ul0007-0002" num="0061"> k=0, . . . , N_i+N_p−2, <br /> and, equation (6) is expressed as <br /><i>r</i>_i<i>=G</i>_i<i>p</i>_m<i>+n</i>_i. <br /> The above embodiment of the system of this invention behaves as a frequency-selective channel, unless the pulse p_m(t) is narrow-band compared to 1/Δτ, as it is the case for OLA-FSK embodiment described hereinbelow. Even when the nodes fire their signals periodically the mobility of the nodes causes changes of the response g_i(t) over time. If most of the network is stationary and N is large, the inertia of the system will be such that mobile nodes will cause small changes in g_i(t). </li></ul></li></ul>

0062Since the transmission channel is bandlimited with passband bandwidth W, the signature waveform p_m(t) will have to be bandlimited and, therefore, uniquely expressible through its samples taken at the Nyquist rate 1/T_c, where T_c=1/W. In general, p_m(t) corresponds to a finite number of samples N_pand is approximately time limited with duration T_p≈N_p/W.

0063For example, in linear modulations (e.g. PAM, QAM and PSK) N_p=1 while N_pis equal to the alphabet size in the case of orthogonal modulations (e.g. FSK). In one embodiment, the system (OLA) response in discrete time can be obtained by sampling at the Nyquist rate the complex envelope of the received signal r_i(t), as shown in U.S. Provisional Patent Application Ser. No. 60/504,845, incorporated by reference herein, and in Anna Scaglione and Yao-Win Hong, <i>Opportunistic large arrays: cooperative transmission in wireless multihop ad hoc networks to reach far distances</i>, IEEE Transactions on Signal Processing, Vol. 51, No. 8, August 2003, pp. 2082-2092, also incorporated by reference herein.

0064It should be noted that although the effect of error and noise propagation at the successive levels of OLA relays has been neglected in the above described embodiment, that is not a limitation of this invention. If a node receives a very weak signal compared to the noise level so that it cannot take reliable decisions or it would mostly increase the noise level for the other receivers, in many embodiments, it remains silent. Further discussions on these issues and the repetition strategy for the regenerative and non-regenerative schemes are described herein below.

0065The transmission of the OLA is led by one or more predetermined source nodes in the network. All the other nodes form multiple stages of relays to either flood the network with the information from the source, or just to pass the information to a remote receiver. The intermediate nodes in OLA have a choice of whether to relay or not, depending on the performance at that node. In order to enhance the understanding of the present invention, an analysis of the effects of regenerative and nonregenerative OLA is presented herein below.

0066In the embodiment of the system of this invention utilizing the regenerative scheme, the OLA nodes has the choice of retransmitting its detected symbol or to stay silent. Only nodes whose pair wise symbol error probability of the ith receiver (not considering error propagation), based on the estimates of all possible signatures G_ip_mand receiver noise variance, is below a fixed upper-bound e, i.e.: <maths id="MATH-US-00004" num="4"><math overflow="scroll"><mrow><mrow><mrow><munder><mi>max</mi><mi>m</mi></munder><mo>⁢</mo><mrow><mi>Pr</mi><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>m</mi><mo>→</mo><mi>μ</mi></mrow><mo>}</mo></mrow></mrow></mrow><mo>≤</mo><mi>ε</mi></mrow><mo>,</mo><mrow><mo>∀</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mi>μ</mi><mo>≠</mo><mi>m</mi></mrow></mrow><mo>,</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><mi>M</mi><mo>-</mo><mn>1.</mn></mrow></mrow></math></maths><br /> reply.

0067In the embodiment of <figref idref="DRAWINGS">FIG. 2</figref><i>d</i>, computer readable code for determining the pair wise symbol error probability of the ith receiver and for comparing the determined pair wise symbol error probability to a predetermined threshold, ε, comprise the means for determining whether to retransmit. In another embodiment of the means for determining whether to retransmit, shown in <figref idref="DRAWINGS">FIG. 2</figref><i>e</i>, a signal <b>155</b>, indicative of the pair wise symbol error probability and determined from the received signal <b>110</b>, is provided from the receiver <b>35</b> to a comparator <b>160</b>. (Such a signal <b>110</b> may be, in one embodiment but not a limitation of this invention, a signal indicative of received energy.) A signal <b>165</b>, indicative of a predetermined criterion, ε, is also provided to the comparator <b>160</b>. The comparator <b>160</b> generates an enabling or disabling signal <b>170</b> which is provided to the transmitter <b>55</b>.

0068In the N_ssamples contained in each symbol period the time instant selected for the detection and subsequent echo is the first sample N_i≦N_sat which the node replies. If there is no such sample the node will never echo the signal (but it may obviously detect the information). The process is illustrated in the following example.

0069Consider a regenerative OLA scenario with 4 nodes as shown in <figref idref="DRAWINGS">FIG. 2</figref><i>a</i>. Let node <b>1</b> be the leader node, and nodes <b>2</b>, <b>3</b>, and <b>4</b> as regenerative relays. In <figref idref="DRAWINGS">FIG. 5</figref>, the aggregated signals received at nodes <b>2</b>, <b>3</b>, and <b>4</b> are sketched. The spikes represent the point where each node achieves its SNR threshold and starts its transmission, this is referred to as the firing instant. Node <b>2</b> only receives the signal transmitted by node <b>1</b> before it achieves the threshold and starts rebroadcasting. Node <b>3</b>, however, receives the accumulation of energy from both nodes <b>1</b> and <b>2</b>, thus, achieves the SNR threshold by just receiving a small portion of the signal from node <b>2</b>. Similarly, node <b>4</b> receives signals from nodes <b>1</b>, <b>2</b>, and <b>3</b>. After the SNR threshold is met (i.e. after the spikes), each node switches to transmitting mode for one symbol period, and does not start receiving until a symbol period T_shas expired. Therefore, the signal coming from later nodes will not be received by the earlier nodes.

0070In order to better describe the method of this invention, the following illustrative example is presented. In one embodiment, each node operates in two modes: (1) the receive phase, in which the node waits until it presumes to provide “reliable” detection of the signal at which point it ‘fires’; and (2) the rest phase, the node silently waits till the end of T_swithout any further transmissions. Thus, with each symbol, each node has the option of retransmitting or opting to stay silent if it believes that the detection will be unreliable. This decision is made at the node based on whether or not it satisfies the predetermined criterion. Thus, the firing time at the node is chosen such that the predetermined criterion is satisfied.

0071For BPSK modulation and a minimum distance detector, the probability of error is solely determined by the Signal to Noise ratio (SNR): <maths id="MATH-US-00005" num="5"><math overflow="scroll"><mrow><mrow><msub><mi>P</mi><mi>BPSK</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>E</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>P</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>m</mi><mo>-></mo><mi>μ</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>Q</mi><mo>⁡</mo><mrow><mo>(</mo><mfrac><mi>d</mi><mrow><mn>2</mn><mo>⁢</mo><mi>σ</mi></mrow></mfrac><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mi>Q</mi><mo>⁡</mo><mrow><mo>(</mo><msqrt><mfrac><mrow><mn>2</mn><mo>⁢</mo><msub><mi>E</mi><mi>b</mi></msub></mrow><msub><mi>N</mi><mn>0</mn></msub></mfrac></msqrt><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths><br /> Since noise is an inherent parameter, noise power N₀given a specific value. The only variable left is the signal energy, E_b. Therefore, in the receive phase, the receiver determines if the upper bound, ε, is satisfied by continuously polling to get an updated reading of the received signal's energy. The firing time is then the instant the signal energy exceeds a threshold.

0072The effect of the error propagation can be included by selecting an appropriate (smaller) ε. Of course, decreasing ε will cause fewer nodes to reply and fewer nodes will contribute to the signal power. Details of the analysis of the effects of error propagation are given in U.S. Provisional patent Application Ser. No. 60/504,845 and in Anna Scaglione and Yao-Win Hong, <i>Opportunistic large arrays: cooperative transmission in wireless multihop ad hoc networks to reach far distances</i>, IEEE Transactions on Signal Processing, Vol. 51, No. 8, August 2003, pp. 2082-2092.

0073In the non-regenerative embodiment, every node that achieves the SNR constraint amplifies the signal coming from the other nodes as well as their receiver noise. Hence, the noise n_iin Equation (6) has a rather complex structure, since it includes the noise that comes from every node that has transmitted previously and all its subsequent amplifications along with the signal. Since the geographical area is limited, the delay spread of each node response will also be limited, as far as the signal to noise contribution is concerned. Considerations on the SNR can be deduced by considering the inherently recursive structure of the signal composition. From Equation (6), the signal received by node i at time k is: <maths id="MATH-US-00006" num="6"><math overflow="scroll"><mrow><mrow><mrow><msub><mi>r</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>0</mn></mrow><mrow><msub><mi>N</mi><mi>p</mi></msub><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mrow><msub><mi>p</mi><mi>m</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>l</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><msub><mi>g</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>k</mi><mo>-</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mo>+</mo><mrow><msub><mi>n</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>,</mo></mrow></math></maths><br /> where n_i(k) includes the noise at the ith receiver plus all the noise contributions that were added at each receiver and propagated through the network up until the kth sample.

0074In one embodiment utilizing non-regenerative repeaters, only nodes in which the signal to noise ratio at the node, SNR_i, is above a fixed threshold, {overscore (ξ)}, that is, SNR_i>{overscore (ξ)} are active in the OLA network. In one embodiment, <maths id="MATH-US-00007" num="7"><math overflow="scroll"><mrow><mrow><mfrac><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>n</mi><mi>i</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow></mfrac><mo>≥</mo><mi>β</mi></mrow><mo>,</mo></mrow></math></maths><br /> where β≧0, g_iincludes all the echoes and n_ithe noise of the nodes that amplified the signal.

0075In one embodiment, the signal energy is (the expectation <br /> is over the symbols): <maths id="MATH-US-00008" num="8"><math overflow="scroll"><mrow><mo>≃</mo><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow><mo>⁢</mo><msup><mrow><mo></mo><msub><mi>A</mi><mrow><mi>p</mi><mo>,</mo><mi>i</mi></mrow></msub><mo></mo></mrow><mn>2</mn></msup></mrow></mrow></mrow></math></maths><br /> and the average noise energy is: <maths id="MATH-US-00009" num="9"><math overflow="scroll"><mrow><mo>≃</mo><mrow><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>n</mi><mi>i</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow><mo>⁢</mo><msup><mrow><mo></mo><msub><mi>A</mi><mrow><mi>p</mi><mo>,</mo><mi>i</mi></mrow></msub><mo></mo></mrow><mn>2</mn></msup></mrow></mrow><mo>+</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>z</mi><mi>p</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow></mrow></mrow></math></maths><br /> From the above, in one embodiment, the signal to noise ratio (SNR) at the pth node can be expressed as <maths id="MATH-US-00010" num="10"><math overflow="scroll"><mtable><mtr><mtd><mrow><mfrac><msub><mi>E</mi><mi>p</mi></msub><msub><mi>η</mi><mi>p</mi></msub></mfrac><mo>≃</mo><mi /><mo>⁢</mo><mfrac><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow><mo>⁢</mo><msup><mrow><mo></mo><msub><mi>A</mi><mrow><mi>p</mi><mo>,</mo><mi>i</mi></mrow></msub><mo></mo></mrow><mn>2</mn></msup></mrow></mrow><mrow><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>n</mi><mi>i</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow><mo>⁢</mo><msup><mrow><mo></mo><msub><mi>A</mi><mrow><mi>p</mi><mo>,</mo><mi>i</mi></mrow></msub><mo></mo></mrow><mn>2</mn></msup></mrow></mrow><mo>+</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>z</mi><mi>p</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow></mrow></mfrac></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mfrac><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow><mo>⁢</mo><msup><mrow><mo></mo><msub><mi>A</mi><mrow><mi>p</mi><mo>,</mo><mi>i</mi></mrow></msub><mo></mo></mrow><mn>2</mn></msup></mrow></mrow><mrow><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mfrac><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>n</mi><mi>i</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow><mo>⁢</mo><msup><mrow><mo></mo><msub><mi>A</mi><mrow><mi>p</mi><mo>,</mo><mi>i</mi></mrow></msub><mo></mo></mrow><mn>2</mn></msup><mo>⁢</mo><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow></mfrac></mrow><mo>+</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>z</mi><mi>p</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow></mrow></mfrac><mo>></mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi /><mo>⁢</mo><mrow><msup><mrow><mo>(</mo><mrow><msup><mi>β</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>+</mo><msubsup><mi>ξ</mi><mi>p</mi><mrow><mo>-</mo><mn>1</mn></mrow></msubsup></mrow><mo>)</mo></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>,</mo><mi>where</mi></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>ξ</mi><mi>p</mi></msub><mo>⁢</mo><mover><mo>=</mo><mi>△</mi></mover><mo>⁢</mo><mi /><mo>⁢</mo><mrow><mfrac><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>p</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>z</mi><mi>p</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow></mfrac><mo>≈</mo><mfrac><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow><mo>⁢</mo><msup><mrow><mo></mo><msub><mi>A</mi><mrow><mi>p</mi><mo>,</mo><mi>i</mi></mrow></msub><mo></mo></mrow><mn>2</mn></msup></mrow></mrow><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>z</mi><mi>p</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow></mfrac></mrow></mrow><mo>,</mo></mrow></mtd></mtr></mtable></math></maths>

0076Since β≧0, taking into account the behavior of the OLA network as the OLA “wave” advances, and setting the threshold, {overscore (ξ)}, high enough to compensate for the loss due to the relaying process, in one embodiment, the SNR condition can be approximated by ξ_i>{overscore (ξ)} where <maths id="MATH-US-00011" num="11"><math overflow="scroll"><mrow><msub><mi>ξ</mi><mi>i</mi></msub><mo>=</mo><mrow><mfrac><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mi>G</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>p</mi><mi>m</mi></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>z</mi><mi>i</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow></mfrac><mo>.</mo></mrow></mrow></math></maths>

0077In the embodiment, for non-regenerative repeaters, of <figref idref="DRAWINGS">FIG. 2</figref><i>d</i>, computer readable code for determining the signal to noise ratio (SNR) (or an approximate value) of the ith receiver and for comparing the determined SNR to a predetermined threshold, {overscore (ξ)}, comprise the means for determining whether to retransmit. In another embodiment of the means for determining whether to retransmit, shown in <figref idref="DRAWINGS">FIG. 2</figref><i>e</i>, a signal <b>155</b>, indicative of the signal to noise ratio (SNR) (or an approximate value) and determined from the received signal <b>110</b>, is provided from the receiver <b>35</b> to a comparator <b>160</b>. A signal <b>165</b>, indicative of a predetermined criterion, {overscore (ξ)}, is also provided to the comparator <b>160</b>. The comparator <b>160</b> generates an enabling or disabling signal <b>170</b> which is provided to the transmitter <b>50</b>.

0078Further details of the signal to noise ratio for the embodiment utilizing non-regenerative repeaters are given in U.S. Provisional patent Application Ser. No. 60/504,845 and in Anna Scaglione and Yao-Win Hong, <i>Opportunistic large arrays: cooperative transmission in wireless multihop ad hoc networks to reach far distances</i>, IEEE Transactions on Signal Processing, Vol. 51, No. 8, August 2003, pp. 2082-2092.

0079In one embodiment, the transmitted signal is linearly modulated. In another embodiment, the modulation of the transmitted signal produces orthogonal signals. In a further embodiment, a modulation method of this invention, Leader Position Modulation, is used. Denote by s_i;m=G_ip_mThe modulation signature of the mth symbol viewed by the ith node is denoted by <br />s_i,m=G_ip_m<br /> The receiver index i is omitted when it is not necessary for the sake of the derivations.

0080Because the receiver does not have exact knowledge of the signal space, the optimum Maximum Likelihood (ML) receiver structure differs from the classic ML receiver in AWGN where it is simply a minimum distance detector. However, when the mean square error (MSE) of the estimates of ŝ_i,mis much smaller than the noise variance N₀, the structural and performance differences between the true ML receiver and the Additive White Gaussian Noise (AWGN) ML receiver will be negligible.

0081In the embodiment in which the transmitted signal is linearly modulated, the leader signal is simply x_mp(t) where x_mis the complex symbol that belongs to an M-ary constellation (QAM, ASK, PSK) and p(t) is a Nyquist pulse with bandwidth W. Thus, with p_m=x_mfrom Equation (9), the received signal at the ith Node is <br /><i>r</i>_i<i>=g</i>_i<i>x</i>_m<i>+n</i>_i.

0082The signal space for the complex envelope is one dimensional (two dimensions in R). Omitting the receiver index i, the ML detection rule is: <maths id="MATH-US-00012" num="12"><math overflow="scroll"><mrow><mrow><msub><mover><mi>x</mi><mo>^</mo></mover><mi>m</mi></msub><mo>=</mo><mrow><mi>arg</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><munder><mi>max</mi><mi>p</mi></munder><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mi>p</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>r</mi><mo>|</mo><msub><mi>x</mi><mi>p</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></math></maths><br /> where p(r|x_p) is the joint probability density function of r given x_m. The joint probability density functions, p(r|x_p), are determined by the error/noise propagation mechanism and by the fact that the receiver has imperfect knowledge of <br /><i>g=ĝ+e. </i>

0083The OLA system is a Spread Spectrum System where the bandwidth of the symbol is much larger than the effective symbol rate. The Spreading Factor of the system is N_s=T_sW. Therefore, the projection <br />r*ĝ<br /> is also effectively equivalent to the despreading of a Direct Sequence Spread Spectrum (DS-SS) signal.

0084Further details of the detection of the linearly modulated OLA signal are given in U.S. Provisional patent Application Ser. No. 60/504,845 and in Anna Scaglione and Yao-Win Hong, <i>Opportunistic large arrays: cooperative transmission in wireless multihop ad hoc networks to reach far distances</i>, IEEE Transactions on Signal Processing, Vol. 51, No. 8, August 2003, pp. 2082-2092.

0085Orthogonal signaling has the appealing property of being power efficient and allowing simple incoherent envelope detection. On-Off Keying (OOK) as well as both Frequency Shift Keying (FSK) and Pulse Position Modulation (PPM) can be implemented in embodiments of the OLA system, as shown in U.S. Provisional patent Application Ser. No. 60/504,845, and in Anna Scaglione and Yao-Win Hong, <i>Opportunistic large arrays: cooperative transmission in wireless multihop ad hoc networks to reach far distances</i>, IEEE Transactions on Signal Processing, Vol. 51, No. 8, August 2003, pp. 2082-2092. In embodiments of this invention that adopt incoherent schemes such as OOK or FSK, the receivers are simply energy detectors and only symbol synchronization is required, but not training.

0086The OLA-PPM embodiment is compatible with an Ultra-Wideband Radio Interface and in this case the OLA system produces a Time-Hopping (TH) code (a sort of bar code that is distinctive of the specific leader triggering the OLA). Further details of the detection of the orthogonally modulated OLA signal are given in U.S. Provisional patent Application Ser. No. 60/504,845, and in Anna Scaglione and Yao-Win Hong, <i>Opportunistic large arrays: cooperative transmission in wireless multihop ad hoc networks to reach far distances</i>, IEEE Transactions on Signal Processing, Vol. 51, No. 8, August 2003, pp. 2082-2092.

0087Multiple clusters of ad hoc wireless nodes can form a multi-OLA system, constructing a multiple access system with the cluster of nodes acting as a team through cooperative transmission rather than transmitting independent data from each node.

0088An embodiment of the OLA system creates a pseudo-noise spreading signature g_iwhich appears to be different depending on the relative positioning of the nodes in the network. If there are M leaders, each leader will generate a different signature at node i, which is hereinafter denoted by <br />g_i^[m]<br /> m=0, . . . , M−1, and, if the positions of the leaders are sufficiently separated and N>>1, the signatures will be likely to have low cross-correlation, exactly as in a multiple access DS-SS system. Even if the transmissions from the leaders are not synchronized, the low cross-correlation among signatures will allow to mitigate the multi-user interference (MUI).

0089An embodiment, which is implemented by a multiple access OLA system, of the method of this invention includes transmitting information from each one of a number of predetermined leader nodes, receiving at each one of the receiving nodes information transmitted from at least one of the number of predetermined leader nodes and information transmitted from other nodes from the receiving nodes, determining at each one of the receiving nodes whether to retransmit the received information, and, retransmitting the received information from each one of the receiving nodes, if retransmitting is determined. In one embodiment, each predetermined leader node is capable of generating a different signature at a location of each of at least some of the receiving nodes. The method can include the regenerative mode and the non regenerative mode disclosed above.

0090Note that there is no difference in terms of timing requirements between the systems of this invention and a classic DSSS physical layer in an asynchronous network. In addition, the probability that a node will to have to react to two different leaders at the same time instant is low. In any case the problem can be easily overcome by letting the nodes give priority to one of the leaders chosen arbitrarily, discriminating them through their signatures.

0091By exploiting the same mechanism, a method of modulation of this invention can be applied if M leaders have access to the same information that has to be forwarded to the remote destinations. In fact, the mth symbol information can be embedded in the signal sm(t) by letting the mth leader transmit a pulse p(t): <maths id="MATH-US-00013" num="13"><math overflow="scroll"><mrow><mrow><msub><mi>s</mi><mi>m</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo>⁢</mo><mrow><msubsup><mi>A</mi><mi>n</mi><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></msubsup><mo>⁢</mo><mrow><mrow><mi>p</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msubsup><mi>τ</mi><mi>n</mi><mrow><mo>(</mo><mi>m</mi><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></mrow></math></maths><br /> This modulation method of this invention is hereinafter referred to as Leader Position Modulation (LPM). In one embodiment, the receiver is trained to receive all the signatures s_m(t) and the asynchronism between the leaders epochs can be taken into account by appropriately extending the duration of the symbol T_sto avoid inter symbol interference (ISI). In any case, the signatures have low cross-correlation and the effect of moderate ISI is going to be mitigated by the spreading-gain.

0092The advantages of LPM are: 1) The leaders and followers just transmit one type of pulse, which simplifies the transmitter scheme; 2) The followers do not have to detect the information from the leader, unless they want to. The followers simply have to transmit the pulse p(t) in response to a power variation in the signal they sense at specific time instants, each associated to a particular leader. This considerably simplifies the operations that the individual nodes have to perform to contribute to the OLA.

0093Embodiments of adaptive receivers for use with the systems of this invention are described below. If the mobility of the transmitters is limited, or at least the large part of the nodes do not change their position and behavior, the signature will have modest variations that the receiver can track adaptively. The signal estimation could be formulated as either a pure waveform estimation problem, or a channel estimation problem of a frequency selective channel. Two embodiments are presented hereinbelow: estimation based on training and blind estimation.

0094Embodiments utilizing Signal Estimation with Training are described hereinbelow. If low probability of detection (LPD) is desired, the leader transmitter can modulate the successive replicas of s_mwith a pseudo-noise sequence c(i) such that |c(i)|=1. Thus, with L training symbols, the symbol estimate can be obtained: <maths id="MATH-US-00014" num="14"><math overflow="scroll"><mrow><mrow><msub><mi>r</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mrow><mrow><mi>c</mi><mo>⁡</mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><msub><mi>s</mi><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub></mrow><mo>+</mo><mrow><msub><mi>n</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mrow><mo>⇒</mo><msub><mover><mi>s</mi><mo>^</mo></mover><mrow><mi>m</mi><mo>,</mo><mi>p</mi></mrow></msub></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mi>L</mi></mfrac><mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>L</mi></munderover><mo>⁢</mo><mrow><mi>c</mi><mo>*</mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow><mo>⁢</mo><mrow><msub><mi>r</mi><mi>p</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><br /> The Mean Square Estimation Error (MSE) for each of the signature waveforms is <maths id="MATH-US-00015" num="15"><math overflow="scroll"><mrow><mi>MSE</mi><mo>=</mo><mrow><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><mrow><msub><mover><mi>s</mi><mo>^</mo></mover><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>-</mo><msub><mi>s</mi><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub></mrow><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mrow><mi>E</mi><mo>⁢</mo><mrow><mo>{</mo><msup><mrow><mo></mo><msub><mi>n</mi><mi>i</mi></msub><mo></mo></mrow><mn>2</mn></msup><mo>}</mo></mrow></mrow><mi>L</mi></mfrac><mo>.</mo></mrow></mrow></mrow></math></maths>

0095The receiver can adaptively update the estimations in a decision-directed mode where the successive symbols will have the same effect as the training data if the decisions are mostly correct. The accuracy will increase as long as the network configuration does not change. More importantly this method allows to track the changes in the network, which necessarily will occur due to the fact that the network is wireless and the nodes are mobile.

0096Blind estimation methods are always important in a decentralized scenario such as wireless ad hoc networks. Without such techniques, when an additional or returning node joins the network it is necessary for the whole system to stop and restart the training phase.

0097To estimate g_ithe receiver can utilize second order subspace identification methods commonly used in array processing. The OLA signature can be estimated as the maximum eigenvector of the correlation matrix of the received vector, which can be estimated using the sample correlation. The channel estimate can be done by repeatedly updating this covariance matrix and using subspace tracking techniques.

0098As previously described, the OLA signaling is a spread spectrum technique, therefore, it is possible to have multiple OLA networks transmitting simultaneously to the same remote receiver. In the embodiment with multiple OLA networks transmitting simultaneously to the same remote receiver, subspace methods can identify the subspace spanned by the OLA signatures and higher order methods (for example, a Constant Modulus Algorithm) can be utilized to separate the sources up to a permutation.

0099An embodiment of the system of this invention that can be applied to the reach back problem includes transmitting information from at least one predetermined leader node, receiving at each one of a number of receiving nodes the information transmitted from the one or more predetermined leader nodes and information transmitted from other receiving nodes, determining at each one of the receiving nodes whether to retransmit the received information, retransmitting the received information from each receiving node, if retransmitting is determined, and receiving at a remote node the information transmitted from the one or more predetermined leader nodes and the information retransmitted from the receiving nodes.

0100An embodiment of the system of this invention that can be applied to the reach back problem is described below. Considering the OLA structure <b>200</b> shown in <figref idref="DRAWINGS">FIG. 6</figref>, the reach back receiver <b>210</b> is simply another node, at i→∞ and the received signal can be expressed as: <br /><i>r</i>_∞<i>=G</i>_∞<i>p</i>_m<i>+n</i>_∞.

0101The reach back node <b>210</b> is special in the sense that it does not participate in the relaying procedure of the embodiment of the OLA system <b>220</b>. Referring to <figref idref="DRAWINGS">FIG. 6</figref>, the OLA system <b>120</b> includes at least one transmitting (leader) node <b>230</b> having a transmitter, a number of receiving nodes <b>240</b>, and a remote (reachback) node <b>210</b> having a remote receiver (the remote receiver can be similar to the receiver at one of the receiving nodes but adapted to receive the remote node signature). Each one of the receiving nodes has a receiver, means for determining whether to retransmit received information, and a transmitter, such as that shown in <figref idref="DRAWINGS">FIG. 2</figref><i>c</i>. Each receiving node is capable of retransmitting information received from at least one transmitting node and information received from other receiving nodes.

0102The reachback node can communicate to the network in a time or frequency division duplex mode, as in the familiar down-link broadcast channel scenario of standard cellular networks. If the error and noise propagation are not considered, <br /><i>E{∥g</i>_∞∥²<i>}=O</i>(<i>N</i>).

0103Even if error and noise propagation are not strictly controlled and that, as a result, SNR_detsaturates to a specific value as N→∞, a gain is achieved over a non-cooperative schemes. In fact, in a system that relies only on point-to-point connections to deliver information, the signals at a far distance are weak compared to the receiver noise, even if they are clean from any additional noise term.

0104In order to better illustrate the method of this invention, a network of 100 nodes inside a square area of 350×350 m²is simulated. The reach back node <b>210</b> is 1 km away from the center of the network <b>220</b>.

0105The BER performance at the remote receiver using a point-to-point link with the nearest node in the network is compared to that obtained using OLA. Each BER value in the simulation is averaged over 10 different network configurations with nodes randomly distributed in the specified area with a uniform distribution.

0106In the simulation each node-to-node transmission is assumed to experience independent small-scale fading with Rayleigh coefficients of variance 1. The large-scale fading is deterministic and the path loss model is based on the model used in ns2 [Network Simulator—ns2 Available at http://www.isi.edu/nsnam/ns/] where the Free Space Model is used for distance d<d_c(the cross-over distance) and the Two-ray Ground Reflection Model is used for d>d_cwhere d_c=4π/λ.

0107<figref idref="DRAWINGS">FIG. 7</figref> shows that reach back communication is impossible without user cooperation, and that the performance improves due to the lower noise level and the reduced error propagation as the SNR threshold increases.

0108It should be noted that the invention is capable of embodiments in which any node has the ability of assuming the role of a leader.

0109In general, the techniques described above may be implemented, for example, in hardware, software, firmware, or any combination thereof. The techniques described above may be implemented in one or more computer programs executing on a programmable computer including a processor, a storage medium readable by the processor (including, for example, volatile and non-volatile memory and/or storage elements), at least one input device, and at least one output device. Program code may be applied to data entered using the input device to perform the functions described and to generate output information. The output information may be applied to one or more output devices.

0110Elements and components described herein may be further divided into additional components or joined together to form fewer components for performing the same functions.

0111Each computer program within the scope of the claims below may be implemented in any programming language, such as assembly language, machine language, a high-level procedural programming language, or an object-oriented programming language. The programming language may be a compiled or interpreted programming language.

0112Each computer program may be implemented in a computer program product tangibly embodied in a computer-readable storage device for execution by a computer processor. Method steps of the invention may be performed by a computer processor executing a program tangibly embodied on a computer-readable medium to perform functions of the invention by operating on input and generating output.

0113Common forms of computer-readable or usable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CDROM, any other optical medium, punched cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave, or any other medium from which a computer can read.

0114It should also be noted that although the embodiments disclosed above can be implemented as wireless systems, this invention is not limited to those systems but it applies to any broadcast medium.

0115Although the invention has been described with respect to various embodiments, it should be realized this invention is also capable of a wide variety of further and other embodiments within the spirit and scope of the appended claims.