Wireless mesh architecture

• US 8,565,164 B2
• Filed: 01/20/2009
• Issued: 10/22/2013
• Est. Priority Date: 02/09/2005
• Status: Active Grant

• Current Assignee: Intellectual Ventures II LLC (Intellectual Ventures LLC)
• Original Assignee: Piccata Fund Limited Liability Company (Intellectual Ventures LLC)
• Inventors: Backes, Floyd
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Shand, Roberta A
• Application Number:
  US12/356,232
• Publication Number:
  US 20130121256A1
• Time in Patent Office: 1,736 Days
• Field of Search: None
• US Class Current: 370/329
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A wireless mesh network architecture includes a plurality of wireless nodes, with each wireless node in the network is connected to every other wireless node in the network. Each pair of wireless nodes is coupled by a link dedicated to exchange of data by the pair of nodes. The link is characterized by an agreement between two end points of the link to rendezvous for the purposes of exchanging data at a predetermined time over a predetermined channel. Methods of negotiating rendezvous characteristics, such as rendezvous channel, time, frequency, duration and transmission power ensure that the selected link is tuned to minimize interference and power usage in the WN. A handshake mechanism enables high performance data delivery with minimal packet loss. The link based architecture uses Link State Advertisements, traffic tags and spanning trees to fine tune packet flow through divergent devices in the network.

Claims

1. A method of establishing a wireless network communication channel between two end points includes the steps of:

the two end points negotiating a rendezvous, including selecting at least one rendezvous channel and rendezvous instance characteristic of the link; and

storing the rendezvous channel and rendezvous instance characteristic at each of the end points of the link;

wherein the rendezvous instance characteristic is a rendezvous duration;

wherein the step of selecting a rendezvous duration includes the steps of at each end point;

selecting a desired rendezvous duration;

receiving a proposed rendezvous duration; and

selecting, as the rendezvous duration of the link, the greater of the desired rendezvous duration and the proposed rendezvous duration.

2. The method according to claim 1, wherein the rendezvous instance characteristics is a rendezvous time.

3. The method according to claim 1, wherein the rendezvous instance characteristic is a rendezvous frequency.

4. The method according to claim 1, wherein the rendezvous instance characteristic is a rendezvous transmission power.

5. The method of claim 1, further including the step of selecting one of the end points to initiate rendezvous in accordance with the rendezvous channel and rendezvous instance information.

6. The method of claim 5 wherein the end point having the lowest Media Access Control (MAC) address is selected.

7. The method of claim 1, wherein the rendezvous is defined as a polling interval of a mesh network transmission window.

8. The method of claim 7, wherein the rendezvous comprises multiple polling inter intervals of the mesh transmission window.

9. The method of claim 8 wherein the multiple polling intervals are associated with different transmission channels.

10. The method of claim 8, wherein the multiple polling intervals are associated with one or more different transmission instance characteristics.

11. The method of claim 1, wherein the method further includes the step of each of the end nodes broadcasting a cost for the link to other nodes in the network to control utilization of the link during routing of packets in the network.

12. The method of claim 11 wherein the cost is communicated as part of a link state advertisement periodically broadcast by an end node.

13. The method of claim 12 wherein the link state advertisement forwarded by an end node includes the ck of only the nodes coupled to the wireless end node to which the wireless end node agrees to route data.

14. A method of establishing a wireless network communication channel between two end points includes the steps of:

the two end points negotiating a rendezvous, including selecting at least one rendezvous channel and rendezvous instance characteristic of the link; and

storing, the rendezvous channel and rendezvous instance characteristic at each of the end points of the link;

wherein the step of selecting a rendezvous channel further includes the step of selecting one or the end points to select the channel including the steps of;

each end point calculating an adjacency vector sum associated with the end point, the adjacency vector sum characterizing a density of wireless nodes near the endpoint;

the, end points exchanging respective adjacency vector sums; and

selecting the rendezvous channel by the end point with the highest adjacency vector sum.

15. The method according to claim 14 wherein the step of selecting the rendezvous channel includes the step of selecting a channel having minimal interference fur a given rendezvous time and rendezvous duration.

16. A wireless mesh network including:

a plurality of wireless nodes, wherein each wireless node is coupled to each one of the other wireless nodes by a dedicated link, wherein a link is characterized by an agreement between two wireless nodes forming end points of the link to rendezvous for the purposes of exchanging data at a predetermined time over a predetermined channel selected to avoid interference with other links associated with the wireless nodes;

wherein each wireless node comprises;

a link table for storing rendezvous information associated with the link; and

a rendezvous controller, coupled to the link table, for controlling transmissions between the wireless node over the links;

wherein each wireless node includes a node map, coupled to the rendezvous controller, for storing identifiers and adjacency vector sums associated with discovered wireless nodes in the network.

17. The wireless mesh network of claim 16 wherein the rendezvous controller further includes logic for controlling negotiation of rendezvous information between the wireless node and another node associated with a link.

18. The wireless mesh network of claim 17 wherein the rendezvous controller uses adjacency vector sum information in the node map to select a channel for the rendezvous.

19. The wireless mesh network of claim 16 further comprising data exchange protocol logic for managing packet transfer by two end points of the link during the rendezvous.

20. The wireless mesh network of claim 16, further comprising logic for identifying costs of the link in the link table.

21. The wireless mesh network of claim 20 wherein the costs stored in the link table may be programmed by the wireless node to preclude routing through the wireless node.

22. The wireless mesh network of claim 20 wherein the costs stored in the link table are obtained in response to link state advertisements received at the wireless node.

23. The wireless mesh network, of claim 16, further comprising buffer logic for storing traffic for a given link pending a rendezvous associated with the link.

24. The wireless mesh network of claim 16 wherein at least one of the wireless nodes is a legacy 802.11 Access Point.