System and method for node-clustering and multi-hop routing in wideband wireless ad-hoc networks

• US 8,031,605 B2
• Filed: 03/31/2008
• Issued: 10/04/2011
• Est. Priority Date: 03/31/2008
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Sandhu, Sumeet, Oyman, Ozgur
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Elallam; Ahmed
• Application Number:
  US12/059,682
• Publication Number:
  US 20090245159A1
• Time in Patent Office: 1,282 Days
• Field of Search: 370/229, 370/231, 370/232, 370/235, 370/236, 370/238, 370/241, 370/252, 455/445, 455/447, 455/450, 455/452.1, 709/241
• US Class Current: 370/235
• CPC Class Codes: H04B 7/2606 Arrangements for base station coverage control, e.g. by using relays in tunnels
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04W 28/22 Negotiating communication rate
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

An ad-hoc network system for computing a proposed number of node-clusters that enable a relative threshold data rate. The ad-hoc network system includes a source terminal, a destination terminal, a plurality of relay terminals, and a cluster determination engine. The source terminal sends a network communication to a destination terminal via a plurality of relay terminals. The cluster determination engine computes a threshold data rate, C, for a number of hops, N, based on a transmission power constraint. The cluster determination engine determines a proposed route for the wireless communication from the source terminal to the destination terminal according to the threshold data rate, C.

Claims

1. A system comprising:

a source terminal configured to generate and send a wireless communication to a destination terminal across at least one of a plurality of relay terminals that are between the source terminal and the destination terminal; and

a cluster determination engine coupled to the source terminal, wherein the cluster determination engine is configured to compute a threshold data rate, C, based on a number of hops, N, and based on a transmission power constraint, wherein the cluster determination engine is further configured to determine a proposed route for the wireless communication from the source terminal to the destination terminal according to the computed threshold data rate, C, and wherein the cluster determination engine is further configured to;

compute the threshold data rate, C, further based on a derivative of the threshold data rate, C, over the number of hops, N;

determine a proposed number of hops, N*, based on the computed threshold data rate, C;

determine a proposed hop distance, D/N, based on the proposed number of hops, N*, wherein D is the distance between the source terminal and the destination terminal and N is the number of hops;

determine the route further based on the proposed hop distance, D/N;

compute a signal-to-noise ratio, Γ

, based on the proposed number of hops, N*; and

partition the source terminal, the plurality of relay terminals, and the destination terminal into a plurality of clusters based on the determination of the proposed hop distance, D/N.

2. The system of claim 1, wherein the cluster determination engine is further configured to compute a per-link average received signal-to-noise ratio, Γ

, based on the proposed number of hops, N*.

3. The system of claim 2, wherein the cluster determination engine is further configured to increase the proposed number of hops, N*, if the computed signal-to-noise ratio, Γ

, is less than a predetermined threshold value.

4. The system of claim 2, wherein the cluster determination engine is further configured to employ multiple-input and multiple-output antennas.

5. The system of claim 1, wherein the cluster determination engine is further configured to perform an ad-hoc route enquiry to discover at least one of a plurality of physical layer channel characteristics and utilize the at least one of the plurality of physical layer channel characteristics to determine the proposed number of hops, the proposed hop distance, the plurality of clusters, and the proposed route, wherein the plurality of physical channel characteristics comprises:

an overall bandwidth between the source terminal and the destination terminal;

a distance between the source terminal and the destination terminal;

at least one operating frequency;

at least one channel bandwidth, wherein the at least one channel bandwidth corresponds to the at least one operating frequency;

at least one path loss exponent, wherein the at least one path loss exponent corresponds to the at least one operating frequency;

a spectrum availability;

a terminal transmission power constraint; and

a terminal power spectral density constraint.

6. The system of claim 1, wherein the cluster determination engine is further configured to store in a lookup table at least one path loss exponent for a specific channel, wherein a path loss exponent function depends on a specific range and a specific carrier frequency, and wherein the cluster determination engine is configured to store a different entry in the lookup table for each available channel.

7. The system of claim 6, wherein the cluster determination engine is further configured to compare a path loss exponent of an available frequency band to a predetermined threshold value, and to employ a Viterbi routing algorithm if the path loss exponent exceeds the predetermined threshold value.

8. The system of claim 1, wherein the cluster determination engine is further configured to employ a spatial reuse process to schedule simultaneous transmissions on a same frequency band by a plurality of terminals over a constructed route.

9. An ad-hoc networking method, comprising:

generating, by a cluster determination engine, data for a wireless communication;

computing, by the cluster determination engine, a threshold data rate, C, based on a number of hops, N, and based on a transmission power constraint, the threshold data rate, C, is further based on a derivative of the threshold data rate, C, over the number of hops, N;

determining, by the cluster determination engine, a route for the wireless communication from a source terminal device to a destination terminal device across at least one of a plurality of relay terminal devices based on the threshold data rate, C;

determining, by the cluster determination engine, a proposed number of hops, N*, based on the threshold data rate, C;

determining, by the cluster determination engine, a proposed hop distance, D/N, based on the proposed number of hops, N*, wherein determining the route is further based on the proposed hop distance, D/N, and wherein D is the distance between the source terminal and the destination terminal and N is the number of hops;

computing a signal-to-noise ratio, Γ

, based on the proposed number of hops N*;

sending, by the cluster determination engine, the generated data to the destination terminal device across the at least one of the plurality of relay terminal devices; and

partitioning the source terminal device, the plurality of relay terminal devices, and the destination terminal device into a plurality of clusters based on the determination of the proposed hop distance, D/N.

10. The method of claim 9, further comprising:

performing an ad-hoc route enquiry to discover at least one of a plurality of physical layer channel characteristics of a new frequency band and utilizing the at least one of the plurality of physical layer channel characteristics of the new frequency band to determine the proposed number of hops, the proposed hop distance, the plurality of clusters, and the proposed route for the new frequency band in response to a switch from a current frequency band to the new frequency band.

11. The method of claim 9, further comprising performing the ad-hoc route enquiry to discover at least one of a plurality of physical layer channel characteristics of each of a plurality of frequency bands and utilizing the at least one of the plurality of physical layer channel characteristics of each of the plurality of frequency bands simultaneously to determine the proposed number of hops, the proposed hop distance, the plurality of clusters, and the proposed route for the plurality of frequency bands.

12. The method of claim 9, further comprising:

performing an ad-hoc route enquiry to discover at least one of a plurality of physical layer channel characteristics; and

utilizing the at least one of the plurality of physical layer channel characteristics to determine the proposed number of hops, the proposed hop distance, the plurality of clusters, and the proposed route, wherein the plurality of physical channel characteristics comprises;

an overall bandwidth between the source terminal device and the destination terminal device;

a distance between the source terminal device and the destination terminal device;

at least one operating frequency;

at least one channel bandwidth, wherein the at least one channel bandwidth corresponds to the at least one operating frequency;

at least one path loss exponent, wherein the at least one path loss exponent corresponds to the at least one operating frequency;

a spectrum availability;

a terminal transmission power constraint; and

a terminal power spectral density constraint.