WO2008095241A1

WO2008095241A1 - Autonomous channel allocation for wireless ad hoc network

Info

Publication number: WO2008095241A1
Application number: PCT/AU2008/000139
Authority: WO
Inventors: Selvakennedy Selvadurai; Satoko Itaya
Original assignee: University of Sydney
Current assignee: University of Sydney
Priority date: 2007-02-07
Filing date: 2008-02-07
Publication date: 2008-08-14
Anticipated expiration: 2009-08-07
Also published as: JP2008193558A

Abstract

The ad hoc wireless network (100) is provided with a plurality of wireless apparatuses (31-55). MPR wireless apparatuses (36-40, 42, 44, 46-50) are the only apparatuses that are able to initiate channel allocation. They each calculate a back-off time. The back-off times will be shorter depending on that MPR wireless apparatuses' criticalness in the network. The all wireless apparatuses in the network then allocate channels in response to channel allocation requests. This allows for autonomous distributed allocation of channels without reference to a gateway, and helps hinder the ripple effect.

Description

" Autonomous Channel Allocation for Wireless Ad Hoc Network"

Field of Technology

This invention relates to wireless ad hoc networks, and more particularly to autonomous channel allocation for wireless ad hoc networks.

Background Art

An ad hoc network, such as a wireless mesh network (WMN), is a network in which communication links between a plurality of wireless apparatuses is autonomously created. If two wireless apparatuses that arc communicating in an ad hoc network are not present in the same communication area, a wireless apparatus located between the two wireless apparatuses functions as a router and relays data packets, thus enabling the formation of a wide area multi-hop wireless network.

Dynamic routing protocols that support multi-hop communications include table driven protocols and on~demand protocols. Table driven protocols create routing tables beforehand that regularly exchange control information relating to routes. FSR (Fish- eye State Routing), OLSR (Optimized Link State Routing) and TBRPF (Topology Dissemination Based on Reverse-Path Forwarding) are such known protocols.

On-dcmand protocols first construct routes to destinations at the point at which data requests are generated. Examples of these protocols include DSR (Dynamic Source Routing) and ΛODV (Ad Hoc On-Dcmand Distance Vector Routing).

The application of a plurality of network interface cards (NICs) has previously been proposed to wireless apparatuses employed in ad hoc networks (Non-Patent References 1 to 3). In Non-Patent Reference 1 , a plurality of network interface cards was applied when identical numbers of network interface cards and channels were present. All wireless apparatuses employ a static identical channel assignment. Thus static channel allocations were performed for all terminals, such that the channel Channel- 1 was allocated to network interface card NIC-t, and channel Charmel-2 was allocated to network interface card NTC-2. This proposal enabled linear expansion of network capacity through the number of network interface cards employed.

Non-Patent Reference 2 proposed a centrally integrated load detecting channel allocation algorithm and routing algorithm for a wireless mesh network in which a gateway that was connected to a wired network was present, and that employed a plurality of network interface cards in an access network that controlled communication to the gateway and communication from the gateway, This assumed the existence of communication profile information For the channel allocations posted. As a result, this demonstrated the feasibility of greater capacity improvement than the linear capacity improvement through the employment of many network interface cards.

Non-Patent Reference 3 proposed an initial distributed channel allocation for an access scenario similar to the aforementioned. By applying higher priority to terminals that were closer to the gateway, such terminals could select channels with lower interference than terminals that were more distant from the gateway.

Local algorithms for similar capacity gain employing two hop adjacent information have been proposed. An important consideration of autonomous distributed channel assignment is the dependency among the neighbouring wireless apparatuses, and the subsequent ripple effect. Fig. 12 shows the channel dependency effect in a specific sample network comprised of nine wireless apparatuses 90 to 98 in a complete grid formation.

Communication links between the wireless apparatuses are shown as a line and the channel allocated for each link, being channel 1 , 2 or 3, is marked on the links. Figure

12(a) shows this network prior to the change in channel allocation and Figure 12(b) shows this network after channel reallocation. In this example wireless apparatus 93 identifies that channel 2 is a better channel for communication with wireless apparatus

94 and decides to switch one of its interfaces. This starts a chain effect in the neighbouring nodes to maintain connectivity in the links between wireless apparatuses

94 and 95, 94 and 97, 96 and 97.

Non-Patent Reference 1 R. Draves, J. Padhye and B, ZiII, 'Routing in multi- wireless, multi-hop wireless mesh networks¹, in Proc. Mohzcom, Philadelphia, PA, USA, 2004, pp.114- 128 Non-Patent Reference 2 A. Raπiwala, K. Gopalan and T.-c. Chiueh,

'Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks', ACMSIGMOBILE Mobile Computing and Communications Review, vol. 8, pp.50-65, 2004

Non-Patent Reference 3 A. Raniwala and TVc. Chiueh, 'Architecture and algorithms for IEEE 802.1 1 -based multi-channel wireless mesh network,' in

Proc, INFOCO M, Miami, FL, USA, 2005, pp.2223-2234

Summary of the Invention

In a first aspect the invention provides a wireless ad hoc network to perform autonomous channel allocation comprising: a plurality of first wireless apparatuses, in order of priority each operable to initiate and perform channel allocation to one or more neighbouring wireless apparatuses by sending change allocation requests; and a plurality of second wireless apparatuses each operable to perform channel allocation in response to a received channel allocation request from at least one first wireless apparatus.

In a second aspect the invention provides a method of autonomous channel allocation for a wireless ad hoc network, the method comprising the steps of: in order of priority, a plurality of first wireless apparatuses each initiating and performing channel allocation to one or more neighbouring wireless apparatuses by sending change allocation requests; and a plurality of second wireless apparatuses each performing channel allocation in response to the channel allocation request received from at least one of the first wireless apparatuses. Each first wireless is apparatus may be operable to determine their own priority.

Each second wireless apparatus may be operable to perform channel allocation based on the order that the channel allocation requests are received.

Hach first wireless apparatus may be a wireless relay apparatus operable to relay packets within the wireless ad hoc network. The priority of each first wireless apparatus may be based on a random back-off time and each first wireless apparatus initiates channel allocation after the lapse of the random back-ofTtirne,

The priority of a first wireless apparatus may be based on the number of wireless apparatuses that operate to request relaying of packets to the first wireless apparatus. Further or alternatively, the priority of a first wireless apparatus may be based on the number of neighbouring wireless apparatuses of the first apparatuses that are first wireless apparatuses.

Each first wireless apparatus may be operable to initiate channel allocation of an available channel of least interference for communication with neighboxjring first wireless apparatuses.

Bach first wireless apparatus may be operable to initiate channel allocation of an available channel, other than an available channel of least interference, for communication with second wireless apparatuses that request relaying of packets to the first wireless apparatus. The first wireless apparatus may be further operable to perform in the same way as a second wireless apparatus. Kach wireless apparatus may have a plurality of interfaces, and allocates different channels to each of the interfaces.

Each second wireless apparatus may be Further operable to broadcast an acknowledgement message to neighbouring apparatuses aAer performing channel allocation.

Each second wireless apparatus may be further operable to broadcast a non- acknowledgement message to neighbouring apparatuses in response to a received channel allocation request when channel allocation has been completed on all interfaces of the second wireless apparatus. The first and second wireless apparatuses may be operable to perform channel allocation at multiple intervals.

The network is a wireless mesh network. A neighbour may be a wireless apparatus with which direct communication is possible,

When channel allocation has been performed on at least one but not all interfaces, each first wireless apparatus may maintain the channel of the interface on which said channel allocation has been performed. When channel allocation has been performed on all interfaces, each first wireless apparatus may maintain the channel allocated to each interface.

In a third aspect the invention is a method for autonomous channel allocation in a wireless ad hoc network at a relaying wireless apparatus having two or more communication interfaces, the method comprising the steps of: waiting a time that is based on a priority of the relaying wireless apparatus among other relaying wireless apparatuses of the network; for each communication interface that does have a channel allocated, allocating an available channel; and sending a channel allocation request to one or more neighbouring wireless apparatuses that communicate with the relaying wireless apparatus using that interface. Il is an advantage of the invention to provide wireless networks that readily enable channel allocation. Using the invention the nomination of a gateway to control channel allocation is not necessary.

The present invention facilitates channel allocation in wireless networks in which no gateway wireless apparatuses are present. In the wireless networks envisaged by the present invention the selected wireless apparatuses determine or are informed of their priority order and initiate channel allocation according to this order. Other wireless apparatuses then allocate channels in respunse to channel allocation requests from at least one of the plurality of first wireless apparatuses. Thus, in the wireless networks envisaged by the present invention, the pluralities of wireless apparatus autonomously allocate channels according to the priority order.

Further, since only first wireless apparatuses are able to initiate channel allocation this helps to hinder the ripple effect within the ad hoc wireless network.

Brief Description of the Drawings

Figure 12 is a schematic drawing of a wireless network showing the ripple effect in channel reallocation.

Λn example of the invention will now be described with reference to the accompanying drawings, in which:

Figure I is a schematic drawing of a wireless network implementing an example of the invention.

Figure 2 is a schematic block diagram showing the constitution of the communication stack of wireless apparatuses shown in Figure 1. Figure 3 shows the format of a packet in the OLSR protocol.

Figure 4 shows the formal of a routing table.

Figure 5 shows the format of a neighbour list.

Figure 6 is simplified flow chart of the method of channel allocation using the invention, Figure 7 is a functional block drawing of channel allocation by each wireless apparatus.

Figure 8 is a drawing showing an MPR group in a wireless network.

Figure 9 is a drawing describing in detail the method of channel allocation.

Figure 10 is a drawing showing average number of channels employed by wireless apparatuses disposed in a mesh format.

Figure 1 1 is a drawing showing the maximum throughput per wireless apparatus in a wireless network in which the wireless apparatuses are disposed in a mesh format.

Best Modes of the Invention In this description identical or equivalent features in the drawings are assigned identical reference numerals, and descriptions of such features is not repeated.

Figure 1 shows a schematic drawing of a wireless mesh network 100 according to this example of the invention, The wireless network 100 provides wireless apparatuses 31-55. The wireless apparatuses 31-55 are disposed in mesh formation in a wireless communication space. Each of the wireless apparatuses 31 -55 comprises, for example, two network interfaces NfFl and NTF2 that are employed to perform wireless communication. Each wireless apparatus consists of two antennas corresponding to the two network interfaces NIFl and NIF2 as described below. The antennas 61-85 are fixed to the wireless apparatuses 31 -55 respectively.

In the wireless network 100, each of the wireless apparatuses 31-55 is able to perform direct wireless communication with the neighbouring wireless apparatuses present in the horizontal direction and the vertical direction, and is not able to perform direct wireless communication with the wireless apparatuses in the diagonal direction. For example, when wireless apparatus 31 performs wireless „ communication with wireless apparatus 55, this can be achieved via wireless apparatuses 32-35, 40, 45 and 50. Alternatively, via wireless apparatuses 3(5, . 41 , 46 and 51 -54, or wireless apparatuses 36, 37, 42, 43, 48, 49 and 50.

In this manner, each of the wireless apparatuses 31 -55 in the wireless network 100 is able to perform wireless communication with destination wireless apparatuses via a plurality of wireless apparatuses, that is by multi-hops. However, in order to increase the volume of communications on the wireless network 100, it would be necessary to allocate different channels to the two network interfaces NlFl and NIF2 of wireless apparatuses 31-55, but such channel allocation is not simple in a wireless network 100 in which no wireless apparatus resembling a gateway is present. Thus a method for readily allocating channels in the wireless network 100 in which no wireless apparatus resembling a gateway is present is described below. This method is also effective at helping reduce the ripple effect within the network 100.

Tn this example, the OLSR protocol is employed as the protocol for establishing wireless communication routes between senders and receivers. The OLSR protocol is a table driven routing protocol and employs Hello messages and TC (Topology Control) messages to exchange routing information and generates routing tables.

Figure 2 is a schematic block diagram showing the configuration of the wireless apparatus 31 shown in Figure 1. The wireless apparatus 31 includes antennas 10, 1 1, an input part 12, an output part 13, user applications 14 and a communication control part 15.

The antennas 10, 1 1 form the antennas 61-85 shown in Figure 1. Each of the antennas 10, 1 1 receives data from other wireless apparatuses via wireless communication space and passes the received data to the communication control part 15, That data is then sent from the communication control part 15 using antennas 10, 1 1 via wireless communication space to other wireless apparatuses. The input part 12 receives the messages and data addresses input by the operator of the wireless apparatus 31 and outputs the received messages and data addresses to the user applications 14. The output part 13 displays the messages according to the controls from the user applications 14. The user applications 14 generate data on the basis of the messages from lhe input part J 2 and the address and output the data to the communication control part 15.

The communication control part 15 consists of a plurality of modules that perform communication control according to the ARFA (Advanced Research Project Agency) Internet hierarchical structure. Thus the communication control part 15 consists of a wireless interface module 16, and a MAC (Media Aceess Control) module 17, and buffers 18, and a LLC (Logical Link Control) module 19, and an IP (Internet Protocol) module 20, and routing tables 21 , and a TCP module 22, and a UDP module 23 and a routing daemon 24,

The wireless interface module 16 belongs to the physical layer and possesses two network interfaces NIFI and N1F2. The wireless interface module 16 performs modulation and demodulation of sent signals and received signals according to specific rules, and employs at least one of the two network interfaces NIFl and NTF2 in order to send and receive, In this case, the two network interfaces NIF 1 and NIF2 are allocated different channels. The MAC module 17 belongs to the MAC layer and executes MAC protocols, performing the following functions. The MAC module 17 also controls the resending of data (packets) and so forth.

The buffers 18 belong to the data link layer and temporarily store packets. The LLC module 19 belongs to the data link layer and executes the LLC protocol and establishes and closes links with neighbouring wireless apparatuses.

The IP module 20 belongs to the Internet layer and allocates by a method described below channels to the two network interfaces NIFl and NIF2 that belong to the wireless interface module 16, The IP module 20 also generates change channel requests in channel allocation processing and broadcasts the channel requests that have been generated.

The IP module 20 also generates IP packets. IP packets consist of IP headers and IP data parts that are intended to hold higher level protocol packets. The IP module 20 receives data from the TCP module 22 and stores such data received in the IP data parts and generates IP packets. The IP module 20 then searches the routing tables 21 according to the OLSR protocol which is a table-driven routing protocol and determines the route for the transmission of the IP packets that have been generated. The IP module then sends the IP packets to the destination along the route that has been determined,

The routing tables 21 belong to the Internet layer and store route information that is associated with destinations as will be described below. The TCP module 22 belongs to the transport layer and generates TCP packets.

TCP packets consist of TCP headers and TCP data parts that store higher level protocol data. The TCP module 22 then sends the TCP packets generated to the IP module 20.

The UDP module 23 belongs to the transport layer and broadcasts the Update packets generated by the routing daemon 24, and receives Update packets broadcast by other wireless apparatuses and outputs them to the routing daemon 24.

The routing daemon 24 belongs to the process/application layer and monitors the execution status of other communication control modules and processes requests from other communication modules.

The routing daemon 24 also calculates optimum routes on the basis of Hello packets received from other wireless apparatuses and dynamically generates routing tables 21 in the Internet layer.

The wireless apparatuses 32-55 shown in Figure 1 possess the same configurations as the wireless apparatus 31 shown in Figure 2.

Figure 3 shows the PKT packet format in the OLSR protocol. PKT packets consist of packet headers PHD and message headers MHD3 , MHD2 ... . PKT packets employ UDP module 23 port No. 698 to send and receive.

Packet headers PHD consist of packet lengths and packet sequence numbers.

Packet lengths consist of 16 bits of data and indicate the number of bytes in the packet.

Packet sequence numbers consist of 16 bits of data and are employed to determine which packets are new. Packet numbers are incremented by ' ] ' whenever new packets are generated. Consequently, a higher packet number indicates a newer PKT packet.

Message headers MHDl, MHD2 ... consist of message types, and effective times, and message sizes, and sender addresses, and TTLs, and numbers of hops, and message sequence numbers and messages. Message types consist of 8 bits σf data and indicate the type of message written in the message body, 0 - 127 being reserved. Effective times consist of 8 bits of data and indicate the times in which messages must be managed after receipt. Effective times consist of sigificantis and exponents.

Message sizes consist of 16 bits of data and indicate message lengths. Sender addresses consist of 32 bits of data and indicate the wireless apparatuses that generated the messages. TFLs consist of S bits of data and specify the maximum numbers of hops over which messages are sent. When messages are sent, TTLs are decremented by T. Messages are not sent if TTLs arc ¹O' or ' 1 '. Number of hops consist of 8 bits of data and indicate the numbers of hops from the source of the message. Thus number of hops is initialty set to '0' and are incremented by T at each transmission. Message sequence numbers consist of 16 bits of data and show the identification number assigned to individual messages. Message sequence numbers arc incremented by ' 1 ' each time a message is generated. Messages are the messages to be sent.

In the OLSR protocol, the PKT packet configuration shown in Figure 3 is employed to send and receive all types of messages. Figure 4 is the format of the routing table 21 shown in Figure 2. Routing tables consist of destinations, next wireless apparatuses and number of hops. Destinations, next wireless apparatuses and number of hops are associated with each other. 'Destinations" indicate the IP addresses of destination wireless apparatuses. 'Next wireless apparatuses^* indicate the IP addresses of the next wireless apparatuses to be sent to when PKTs are sent to destinations. 'Number of hops' indicates number of hops to the destination. For example, in Figure 1, when wireless communication is performed between wireless apparatus 31 and wireless apparatus 55 over the route 31, 32, 33, 34, 35, 40, 45, 50 and 55, '7' is stored as the number of hops in the routing table 21 in the wireless apparatus 32. Figure 5 is a table formal showing neighbour list NTBL. Neighbour lists NTBL include own addresses and the addresses of neighbouring wireless apparatuses. Own addresses and addresses of neighbouring wireless apparatuses are associated with each other. 'Own addresses' consist of the IP addresses of the wireless apparatuses that generate neighbour lists NTBL. 'Addresses of neighbouring wireless apparatuses' consist of the IP addresses of wireless apparatuses that are adjacent to the wireless apparatuses that generate neighbour lists NTBL.

In the present invention, each of the wireless apparatuses 31-55 generates routing tables 21 according to the OLSR protocol. When the wireless apparatuses 31- 55 generate routing tables 21, the wireless apparatuses send and receive Hello and TC messages.

Hello messages arc sent regularly in order to distribute information possessed by each of the wireless apparatuses 31-55. By receiving such Hello messages, each of the wireless apparatuses 31-55 is able to collect information concerning the surrounding wireless apparatuses and is able to identify which wireless apparatuses are present in its own surroundings. In OLSR protocol, each of the wireless apparatuses 31-55 manages local link information. Hello messages arc for the purpose of building and sending such local link information. Local link information includes link groups, neighbouring wireless apparatus groups, 2-hop neighbouring wireless apparatus groups and link groups to such wireless apparatuses, and MPR groups.

Link groups are links to groups of wireless apparatuses (neighbouring wireless apparatuses) that directly carry wireless waves, and each link is represented by effective times for sets of addresses between two wireless apparatuses. Effective time is also employed to indicate whether a link is one-directional or two-directional. Neighbouring wireless apparatus groups are composed of addresses of neighbouring wireless apparatuses and the willingness of such neighbouring wireless apparatuses to resend. 2-hop neighbouring wireless apparatus groups are groups of wireless apparatuses that are adjacent to the neighbouring wireless apparatuses.

Multi point relay (MPR) groups are groups of wireless apparatuses that are MPR and are selected as they form the backbone of the network used for relaying data. They are selected to enable the sending of packets PKT to all of wireless apparatuses 31-55 with the minimum necessary number of transmissions when packets PKT are to be sent to all the wireless apparatuses 31-55 in the network 100.

In this invention, MPRs are the only wireless apparatuses that are able to initiate channel assignment processes (first plurality of wireless apparatuses). Good selection of the MPR group is important as a bulk of the bandwidth is afforded u> them. The size of the MPR group should be small with respect to the network size, and suitably located to be able to perform compatible assignment. Thus, a wireless apparatus reorders the neighbour list NTBL in descending order of degree. This order simplifies the selection of the MPR reference set. A higher degree wireless apparatus covers more two-hop neighbouring wireless apparatuses, and such an apparatus is more suitable as an MPR candidate. Based on the ordered neighbour list NTBL, a reference set of MPRs is selected such that all two-hop neighbouring wireless apparatuses are covered. Once this reference set of MPRs is determined, the channel assignment process can be initiated from these MPRs.

The method of the invention to perform channel allocation will now be described with reference to the flow chart of Figure 6.

Broadly speaking, the process of establishing local link information 300 is as follows. At the initial stage, Hello messages are messages containing the addresses of wireless apparatuses sent to neighbouring wireless apparatuses in order to notify each of the wireless apparatuses 31-55 of their presence. This is performed by each of the wireless apparatuses 31-55, and each of the wireless apparatuses 31-55 establishes the wireless apparatuses adjacent to it and their addresses. Link groups and neighbouring wireless apparatus groups are built in this manner.

The local link information that is built is regularly sent out in Hello messages again. Through the repetition of this, it gradually becomes clear whether links are two- way and which wireless apparatuses are at the end from the wireless apparatus. The wireless apparatuses 31 -55 store the local link information that gradually been built in this manner.

Next, MPRs arc selected 302. MPR information is also regularly sent by Hello message and is posted to each of the wireless apparatuses 31 -55. Each of the wireless apparatuses 31-55 is a wireless apparatus requesting the resending of the packet PKT that it has sent, and numbers of wireless apparatuses are selected as MPR groups from among neighbouring wireless apparatuses. Information on these MPR groups is then sent by Hello message to neighbouring wireless apparatuses, and hence wireless apparatuses receiving such Hello messages manage the groups of wireless apparatuses that have selected themselves as MPK as MPR selector groups. In this manner, each of the wireless apparatuses 33-51 is immediately aware of whether it should resend a packet received from any wireless apparatus.

When the sending and receiving of Hello messages builds local link groups in the wireless apparatuses 33-51, TC messages that notify the overall topology of the entire wireless network 100 are sent to the wireless apparatuses 31-55. Such TC messages arc sent regularly by all wireless apparatuses selected as MPR. Thus, because TC messages include links between each wireless apparatus and MPR groups, all the wireless apparatuses 31 -55 in the wireless network 100 arc able to know all the MPRs, and are able to know the overall topology of the wireless network 100 on the basis of all the MPRs, The wireless apparatuses 31 -55 employ the overall topology of the wireless network 100 to calculate shortest routes and creating route tables on that basis.

The wireless apparatuses 33-51 frequently exchange TC messages as distinct from Hello messages. MPR is also used in exchanges of TC messages.

The wireless apparatuses 31-55 send and receive such Hello messages and TC messages, recognize the overall topology of the wireless network 100 and calculate shortest routes on the basis of the recognized wireless network 100 overall topology, and on that basis dynamically generate the routing tables 21 shown in Figure 4. Figure 7 is a functional block diagram of channel allocation in the wireless apparatuses 31 -55. The IP modules 20 in the wireless apparatuses 31-55 include channel allocation means 201 and timers 202. The wireless interface modules 16 in the wireless apparatuses 31-55 include network interfaces NIFl and NIF2, The network interface NlFl is connected to antenna 10 and the network interface NIF2 is connected to antenna 11. Since only the MPRs are able to initiate channel allocation, this introduces some control into the channel allocation process and helps hinder the ripple effect. We also need to minimise parallel assignments by neighbouring nodes. Such ordering to the channel allocation requests is achieved using a back-off function, This ordering imposes a priority among the M(PRs. The MPRs that have a shorter back-off time period have a higher priority than those with a longer back off period.

The back-off period function allows MPRs with more neighbours to assign channels earlier (higher priority) than other MPRs due to their higher level of criticalπess. As the same time, the back-off function provides a bigger time period (and lower priority) if the MPR has in its neighbourhood more wireless apparatuses that are themselves MPR.

The channel allocation means 201 calculates back-off time b(c,,mi) according to the following back-off time formula, Formula (1 ):

In Formula (1), ct ≡ \\,d] is the number of wireless apparatuses that have the selected wireless apparatus / as MPR (i.e. the number of wireless apparatuses that are neighbours to i and are not MPR), and w,- e [\,cf] is the number of wireless apparatuses that are neighbours to / and are MPR. r is a random integer within the range [0,∞], d is the average terminal degree, and s is a scaling factor. . slot _iimβ is the average per-hop round-trip delay.

The channel allocation means 201 relies on the timer 202 for the measurement of the calculated back-off time h(ci,mi) when the channel allocation means calculates back-off time b(ci,m{). This algorithm performs best if the aim of the back-off function is to minimise contentions, where a contention refers to neighbouring MPRs making parallel incompatible channel assignment decisions. To reduce the probability of such an event, a simple analysis is given to guide the configuration of the scaling factor 5. Due to the chosen slotted back-off function, parallel assignments may only happen if more than one MPR randomly chose the same back-off time. In the worst case, all the neighbours of a wireless apparatus might be MPRs, which also implies that fewer wireless apparatuses selected this wireless apparatus as a MPR. As such, the denominator of the ration term in Formula (1) is bound by a small constant factor of wireless apparatus degree, i.e. (c+m) approaches d asymptotically, and thus the term reduces to 5. The back-off function itself reduces to selecting a slot in range [0,s). Say wireless apparatus i backs off for k slots. If A" be the random variable of neighbouring MPRs selecting the same back-off window, it will be binomial Iy distributed with parameters ρ ^∞\ls and n — d. Thus, the expected number or wireless apparatuses is:

To minimize the number of parallel assignments, this expectation should be smaller than one. Accordingly, the scaling constant s should be set such that s»d.

When a wireless apparatus' back-off time is the first to expire in its neighbourhood, it has the option to choose the least interfered channels for both its NIFs as there arc no restraining requests from any neighbours 306,

To ensure an interference aware allocation, each MPR maintains the current interference level of non-overlapping channels from the periodic two-hop neighbourhood information exchanges. The channel allocation means 201 receives Hello packets from the routing daemon 24, and on the basis of the Hello packets received, detects information for wireless apparatuses within a 2-hop range of the wireless apparatus in which it is mounted, and on the basis of the detected information for wireless apparatuses within a 2-hop range, determines the interference of each available channel. More specifically, the channel allocation means 201 employs a sniffer (trademark) to investigate the degree of congestion of packets sent and received by these channels and sets a value to each channel representative of interference and in this example, the lower the value the less the interference.

When the timer 202 calculates the back-off time h(cι,mj, the channel allocation means 201 allocates channels to the network interfaces NIFl and N If 2. More specifically, the channel allocation means allocates the least interfered channel to the network interface (either network interface NIF I or NIF2) that is performing wireless communication with an MPR wireless apparatus, and allocates the next least interfered channel to the other network interface .

Moreover, when the channel allocation means 201 allocates channels to the network interfaces NIFI and NIF2, it generates and broadcasts a change channel request CHANGE CHAN that shows details of the channel allocation mainly containing a table of wireless apparatus to channel mappings.

The timer 202 measures the back-oft^* time b(c_uini) in response to requests from the channei allocation means 201 and when calculation of the back-off time bfami) is complete, outputs an EXPIRE expiry signal showing that back-off time h(a,mi) has expired to the channel allocation means 201.

The channel interlaces NIFl and NIF2 employ the channels received from the channel allocation means 201 for sending and receiving packets.

When a further MPR's calculated back-off time expires and finds one of its interfaces is already constrained by a CHANGE_CHAN request 308 (in this case NIF- 1), it just needs to choose one least interfered channel for its other interface (in this ease NIF-2) 206. The MPR then maps all its neighbouring MPRs to NlF-I, and the non . MPR wireless apparatuses to NIF-2. This is the form of greedy load balancing practiced by each MPR, A CHANGFJ-CHAN request is then broadcasted about the impending channel change request to its neighbours,

When yet a further MPR's calculated back-off time expires and finds that both of its interfaces are already constrained by pervious CHANGE_CHAN requests from its neighbouring MPRs 308, it abstains from any further channel changes for now.

When an MPR receives two CHANGE_CHAN requests, this implies that all its channels are constrained by its own neighbouring MPRs, and further assignment by that MPR would result in network partitions. The possibility of receiving more than two requests is minimised due tp the adopted back-off function. Thus, even if there arc more than two MPRs in the neighbourhood, the first two CHANGE_CHAN requests have priority and would suppress any further channel assignment need, This process is summarised by the following algorithm, Algorithm ( 1 ):

if (an MPR) {

Il is an MPR; so can initiate CHANGE_CHAN Get all channels status if (all NIFs yet to assign ) {

Il need to assign for NIF- 1 and -2 Select best channels for NIFs for (all neighbours) {

Assign least interfered channel for its neighbouring MPRs (NlF-I) Assign next least interfered channel for its remaining neighbours (N1F-2) }

Broadcast CHANGE JZHAN to neighbours / else if (only one NIF does not have a channel allocated) { I! need to assign channel for N1F-2 only

Select least interfered channel for N/F-2 (not identical to channel assigned to NIF-I)

for (all neighbours) {

Maintain channel allocation on NIF-I for its other MPRs Assign channel allocations for NIF-2for its non-MPR neighbours /

Broadcast CHANGE_CHΛN to neighbours

} }

When a wireless apparatuses receives a CHΛNGE-CHΛN request, it will only process the message if the sender is one of its MPRs or one its neighbouring wireless apparatuses (i.e. a member). If a wireless apparatus receives its first request to change, this is a compatible assignment 308, Instead of just replying to its sender, the wireless apparatuses broadcasts an ACK acknowledgement for an accepted request, An ACK also contains a table of wireless apparatus to channel mappings. This aims to ensure its other MPRs become aware of this imminent change. The node subsequently updates its neighbour table to reflect the new channel to use for this sender via NlF-I .

If a second CHANGE_CHAN request for a different channel is received by a wireless apparatus 308, this wireless apparatus is now fully constrained by the requests, and no further request can be accommodated in this round. Before responding the wireless apparatus equally maps the rest of its neighbours between these channels for load balancing. An ACK with the mappings is them broadcasted as above.

Due to the stochastic nature of the proposed assignment and wireless channel uncertainties, a wireless apparatus may receive a request for a third channel with a small probability. If this change request is effected, the assignment would result in a topology change as well as routing information inconsistency among neighbours, In this case the wireless apparatus is made to refuse 308 the change request by sending back NACK non-acknowledgement to allow the sender wireless apparatus to rollback to the previous state. The rollback is possible as the channels arc not assigned immediately, but rather when an ΛCK is received. The algorithm for the response process is given in the following algorithm, Algorithm (2);

if (CHANGEJCHAN from my MPR or my member) {

Il process only when received from my MPR or my member if (first request) { Assign selected channel to NIF-I

Update neighbour table for sender Broadcast A CK to neighbours ϊ else if (second request for distinct channel) { Assign selected channel to NIF-2.

Update neighbour table far sender for (all neighbours) { Il all NIFs assigned; perform greedy load balancing

Assign channels alternately for rest of neighbours ;

Broadcast ACK to neighbours

} else {

Il incompatible assignment request Send NA CK to sender to rollback

} }

Figure 8 is a drawing showing the MPR wireless apparatuses in the wireless network 100. Wireless apparatuses 36-40, 42, 44 and 46-50 form an MPR group and the figures written above these MPRs are their members, that is, the reference numbers of the wireless apparatuses that request that MPR to rcsend packets.

For example, wireless apparatus 36 is able to receive and resend broadcast packets from wireless apparatuses 31, 37 and 41. Also, wireless apparatus 37 is able to receive and resend broadcast packets from wireless apparatuses 32, 36, 38 and 42. When the wireless apparatuses 31-55 that form the wireless network 100 in which an Ml¹R group is present are activated, each of the MPR wireless apparatuses

36-40, 42, 44, 46-50 calculates a back-off time b(a,mi) according to Formula (1), and when those back-off times b(Ci,mO have expired, allocate the least interfered channels to their own unallocated network interfaces NIFl and NIF2.

More specifically, the channel allocations means 201 in the MPR wireless apparatuses calculate random back-off times b(cumi) with Formula (1) and request the measurement of the calculated back-off times b(ci,rni) from the timers 202, The timers 202 in the MPR wireless apparatuses measure the back-off times b(c_ltmj in response to the requests from the channel allocation means 201, and when measurement of the back-off times bfaim) is complete, output EXPIRE expiry signals indicating that the back-off limes b(ct,mt) have expired to the channel allocation means 201.

The channel allocations means 201 in MPR wireless apparatuses then allocates the least interfered channels to their unallocated network interfaces NlFl and N1F2 in response Io the EXPIRE expiry signals from the timers 202.

The MPR group broadcasts through TC messages in the wireless network 100, and because each of the wireless apparatuses knows the topology of the wireless network 100, they detect which of the neighbouring wireless apparatuses are MPR (that is, they are able to detect mi). Moreover, the wireless apparatuses establish local link information and the local link information can detect the number of wireless apparatuses (that is, they can detect ci) that requested a wireless apparatus to resend packets. Moreover, r in Formula (1) is an integer randomly selected from [0,αo] and d, s and slot_time are constants. Therefore MPR wireless apparatuses are able to calculate their respective back -off time b(c_itm) according to Formula (1) 304. When wireless apparatuses 31-51 arc disposed in a complete mesh format, d is set to '4'.

The lengths of the b(cι,mϊ) calculated vary depending on the value of c, and m,- as described above with reference to Formula (1), TheTβ is a high probability that the length of the back-off time b(a,mj) will decrease as C₁ and mi increase and there is a high probability that the length of the back-off time b(cι,mι) will increase as C,- and rtti decrease. c₁ indicates the number of wireless apparatuses that has selected node / as its MPR for rcscnding its requests.. A high value for ci indicates that there is a large number of wireless apparatuses requesting resending of packets to wireless apparatus /, and hence those MPR wireless apparatuses that are requested to resend packets by more wireless apparatuses allocate channels to the network interfaces NIFl, NIF2 with relatively faster timings. If ,or example, wireless apparatus 47 is requested to resend packets in this manner by four wireless apparatuses 42, 46, 48 and 52 and wireless apparatus 46 is requested to reseπd packets in this mariner by two wireless apparatuses 47 and 51, wireless apparatus 47 allocates channels to the network interfaces NIFl, NIF2 with a relatively faster timing than wireless apparatus 46. Moreover, m,- other than '0' indicates that at least one wireless apparatus neighbouring wireless apparatus / is MPR.

A high value for m_t indicates that a relatively large number of the wireless apparatuses neighbouring wireless apparatus i are MPR, and therefore wireless apparatus / allocates channels to the network interfaces NIFl, NTF2 with a relatively faster timing than a wireless apparatus of which relatively few or no neighbouring wireless apparatuses are MPR. For example, three wireless apparatuses 38, 40 and 44, of the four wireless apparatuses (34, 38, 40 and 44) that neighbour wireless apparatus 39 are MPR, and two wireless apparatuses 39 and 49, of the four wireless apparatuses (39, 43, 45 and 49) that neighbour wireless apparatus 44 are MPR. Therefore wireless apparatus 39 allocates channels to the network interfaces NIFl, NIF2 with a faster timing than wireless apparatus 49.

Wireless apparatuses 37, 39, 47 and 49 possess the same q and m₍ but because r in Formula (1) is an integer selected randomly from [0,∞], there is a low probability of the back-off times calculated by wireless apparatuses 37, 39, 47 and 49 all being identical.

Thus in the wireless network 100, generally wireless apparatuses 37, 39, 47 and 49 allocate channels to the network interfaces NIFI, NIF2 with the fastest timing, wireless apparatuses 38 and 48 allocate channels to the network interfaces NIFl, NIF2 with the second fastest liming, wireless apparatuses 36, 40, 46 and 50 allocate channels to the network interfaces NIFI, NIF2 with the third fastest timing, and wireless apparatuses 31-35, 41, 43, 45 and 51-55 allocate channels to network interfaces (either of network interfaces NIFl or NIF2) .

Consequently the present invention readily enables the allocation of channels, even without including gateways. The allocation of channels to the network interfaces NIFl, NTF2 is now described in greater detail with reference to Figure 9. Wireless apparatuses 31-33, 36- 38 and 41-43 are disposed in a mesh format within the same scope of communication. The numbers assigned to MPR wireless apparatuses 36-38 and 42 in Figure 9 are the priority ordering based on the calculated back-off time, where wireless apparatus 37 has a shorter back-ofl^'time than wireless apparatus 42. With the shortest back-off time, wireless apparatus 37 allocates the least interfered channel, ChI , to its network interface NlF 1 , and the second least interfered channel, Ch2, to interface NIF2.

In this case, the channel allocation means 201 of wireless apparatus 37 allocates 5 channel Ch I to network interface NIFl for wireless communication with wireless apparatuses 36, 38 and 42 because these wireless apparatuses 36, 38 and 42 are also MPR. Wireless apparatus 37 allocates channel Ch2 to network interface NIF2 for wireless communication with wireless apparatus 32 which is not MPR, Thus the channel allocation means 201 of the wireless apparatus 37 that makes the initial

10 channel allocation of different channels ChI, Ch2 to the two network interfaces NlF 1, NIF2. To do this, the channel allocation means 201 generates the change channel request

CHANGB_CHANl=[NIFl(Chl)→IPaddress36,[Paddress38,lPaddress42/NlF2(Ch2) — >IPaddress32/ΪPaddress37] and sends it to neighbouring wireless apparatuses 32, 36,

15 38 and 42.

The channel allocation means 201 of wireless apparatuses 32, 36, 38 and 42 receive the request CHANGR_CHAN1 sent from wireless apparatus 37.

The channel allocation means 201 of wireless apparatus 32 references the request CHANGE_CHAN1 received from wireless apparatus 37, determines that the 0 network interface employed by wireless apparatus 37 for wireless communication with wireless apparatus 32 and detects that it has been allocated to channel Ch2.

The channel allocation means 201 of wireless apparatus 32 then determines that the network interface used for wireless communication with wireless apparatus 37 will be network interface NIF 1 and allocates channel Ch2 to network interface NIFl . 5 The channel allocation means 201 of wireless apparatus 32 then generates an acknowledgement ACK I=[NIF I (Ch2)→IPaddress37/lPaddrcss32] showing the details of the channel allocation in wireless apparatus 32 and this acknowledgement ACKl is broadcast to the neighbours.

Assume wireless apparatus 38 has the next shortest back-off time. The channel 0 allocation means 201 of wireless apparatus 38 performs channel allocation following wireless apparatus 37 in response to the CHANGE_CHAN1 request received. More specifically, the channel allocation means 201 of wireless apparatus 38 references the request CHANGE_CHAN1 and detects that wireless apparatus 37 has allocated channel ChI to network interface NlFl for wireless communication between itself and 5 wifeless apparatus 37, The channel allocation means 201 of wireless apparatus 38 then determines that its network interface NlFl is to be the network interface for wireless communication with wireless apparatus 37 and allocates channel Ch1 to network interface NIFl . Wireless apparatus 38 also determines network interface NIF2 for wireless communication with the non-MPR wireless aρρaralu$es 33, 43 and allocates the next least interfered channel available to wireless apparatus 38, in this case Ch3, to network interface NIF2.

The channel allocation means 201 of the wireless apparatus 38 then generates a change channel request

CHANGE_CHAN2=[NIFl(Chϊ)→IPaddress37/NIF2(Ch3)→IPaddrβss33,IPaddfess43 /lPaddress383 showing Lhe details of the channel allocations in wireless apparatus 38. This request CHANGE_CHΛN2 is broadcast to the neighbouring wireless apparatuses 33, 37 and 43.

Wireless apparatus 33 receives the change channel request CHANOE_CHAN2 Prom wireless apparatus 38, Wireless apparatus 33 processes CHΛNGE_CHAN2 similarly to the way that wireless apparatus 32 processed CHANGE_CHAN 1. Accordingly, wireless apparatus 33 generates and broadcasts an acknowledgement ACK2=[NIFl (Ch3)→lPaddress38/lPaddress33].

Wireless apparatus 43 receives and processes the request CHANGE_CHAN2 in the same way as wireless apparatus 33 to generate and broadcast an acknowledgment ACK3=[NIFl (Ch3)->lPaddress38/IPaddress43]. Next, the wireless apparatus 36 processes the request CHANGE_CHAN1 similarly to wireless apparatus 38 to generate and broadcast a request CHANGE_CHAN3=[NIF1(Ch1)→IPaddress37/NIF2(Ch4)→IPaddress3 l _>TPaddress4l /IPaddress36]. Channel Ch4 is selected by wireless apparatus 36 as that is the next least interfered channel available to wireless apparatus 36. Wireless apparatus 31 receives the request CΗANGE_CHAN3 from wireless apparatus 36 and processes it much in the same was as wireless apparatus processed ACK.2. Wireless apparatus 31 processes CHANGE_CHAN3 to generates and broadcast an acknowledgement ACK4=[NIFl(Ch4)->lPaddress36/rPaddress31].

In the same way as wireless apparatus 31, wireless apparatus 41 receives and processes the request CHANGE_CHAN3 to then generate and generate acknowledgement ACK5=[NIFl(Ch4)→IPaddress36/IPaddress41].

The channel allocation means 201 of wireless apparatus 42 also processes the received CHANGR_CHANl in much the same way as wireless apparatus 38. Wireless apparatus 42 generates and broadcasts a request CHΛNGH_CHAN4^[NlFl(Chl)-*IPaddres337/NIF2(Ch3)→lPaddres841 ,IPaddress43 /IPaddress42], Wireless apparatus 41 receives the request CHANGE CHAN4 and processes it to generate and broadcast ACK6=[N1F1 (Ch4)→IPaddress36,ΪPaddress42/IPaddress4 ] ],

Wireless apparatus 43 also receives the request CHΛNGE CHΛN4 and processes it to generate and send an acknowledgement ACK7=[N IFI (Ch3)-»iPaddress38/NIF2(Ch4)->IPaddress42/IPaddress43].

The acknowledgement messages are used to mutuatly confirm the channel allocations to which network interfaces NlFl, N1F2 that will be used in communication with their neighbouring wireless apparatuses,

For example, wireless apparatus 38 receives the acknowledgements ACK3 from wireless apparatus 43 and receives the ACK2 from wireless apparatus 33.

The channel allocation means 201 of wireless apparatus 38 then determines on the basis of the ΛCK3 that the network interface NIP1 of wireless apparatus 43 is used for wireless communication with network interface NIF2 of wireless apparatus 38 using channel Ch3. On the basis of ACK2 wireless apparatus 38 also determines that the network interface NlFl of wireless apparatus 33 is used for wireless communication with network interface NIF2 of wireless apparatus 38 using channel 3.

As a further example, the channel allocation means 201 of wireless apparatus 42 then determines on the basis of ACK.6 that network interface NIFl of wireless apparatus 41 i$ used for wireless communication with network interface NIF2 of wireless apparatus 42 using channel Ch4. It also determines on the basis of ACK7 that network interface NIF2 of wireless apparatus 43 is used for wireless communication with network interface NTF2 of wireless apparatus 42 using channel 4.

As a result of the channel allocations in wireless apparatuses 31 -33, 36-38 and 41 -43 described above, the channels in wireless apparatuses 31 -33, 36-38 and 41 -43 are allocated as shown in Figure 9.

Each of wireless apparatuses 31 -33, 36-38 and 41-43 then perform wireless communication with the neighbouring wireless apparatuses by employing the channels allocated 310,

Duo to the dynamic nature of the channel characteristics in a wireless network, the channel allocation process is repeated and the channel allocations of the network are reinitiated at intervals 312. Changes in allocations would be based on changes in the relative interference levels of the available channels.

The characteristics of the wireless network 100 when channel allocations are performed in this way are now described. The model employed for the evaluation of the characteristics is a 9x9 grid network in which 60 wireless apparatuses are randomly disposed and the scope of communication is fixed as 10 m in relation to a plane 100 m x 100 m. As a result, each wireless apparatus is able to communicate with neighbouring wireless apparatuses within four hops.

The average number of channels used and maximum throughput when the wireless apparatuses allocate channels are now examined in such a wireless network. Figure 10 is a graph showing the average numbers of channels used by wireless apparatuses disposed in a mesh format, In Figure 10 the horizontal axis represents topology and the vertical axis represents the average numbers of channels used. The line kl represents the average numbers of channels used when channels are allocated as envisaged by the present invention, the line k2 represents the average numbers of channels used when single channel allocation is performed and the line k3 represents the average numbers of channels used when two channels similar to the number of network interfaces are allocated,

The results in Figure 10 show that, when single channel allocation is performed, the average number of channels used is ' V and when two channels are allocated, the average number of channels used is '2'. However, when channel allocation is performed as envisaged by the present invention, the average number of channels used is between 1.5 and 2.

Figure 1 1 is a graph showing the maximum throughput per one wireless apparatus in a wireless network consisting of wireless apparatuses disposed in a mesh format. In Figure 1 1 the horizontal axis represents topology and the vertical axis represents maximum throughput. The line k4 represents maximum throughput when channel allocation is performed as envisaged by the present invention, the line k6 represents maximum throughput when single channel allocation is performed and the line k5 represents maximum throughput when two channel allocation is performed, The results in Figure 1 1 show that maximum throughput is greatest when channel allocation is performed as envisaged by the present invention.

Thus maximum throughput is improved by channel allocation as envisaged by the present invention.

In the present invention as described above, when a wireless network 100 consisting of wireless apparatuses 31-55 disposed in a mesh format is activated, those of the wireless apparatuses 31-55 that are MPR wireless apparatuses, namely wireless apparatuses 36-40, 42, 44, 46-50, calculate back-off time b(ci,mø according to the number Q of wireless apparatuses that send packet resend requests to them and the number m,- of neighbouring MPR wireless apparatuses, and allocate channels in sequence beginning from the shortest calculated back-off lime b(q_tm$. Thus there is a lu^'gh probability that back-off time b(c_bmi) will become shorter as the number c,- of wireless apparatuses that send packet resend requests to them increases and the number m,- of neighbouring MPR wireless apparatuses increases.

Consequently the allocation of channels in sequence beginning from the shortest calculated back-off time b(ci,mi) is equivalent to allocating channels in sequence of greatest numbers of wireless apparatuses sending packet resend requests to the wireless apparatus and/or in sequence of greatest numbers of neighbouring MPR wireless apparatuses.

In the foregoing description, the wireless network 100 was provided with wireless apparatuses consisting of MPR that initially allocated channels and non-MPR wireless apparatuses that received channel change requests from MPRs and allocated their own channels, but lhe present invention is not limited thereto, and priorities for the allocation of channels may bo mutually determined, and a plurality of first wireless apparatuses that allocate channels sequentially for high priority as determined, and a plurality of second wireless apparatuses that allocate channels in response to channel change requests from at least one of the plurality of first wireless apparatuses may be provided. Moreover, the priority in the plurality of first wireless apparatuses may be determined by the user of the wireless network 100 and may be preset as the initial setting in the plurality of first wireless apparatuses. Thus in the wireless network 100 envisaged by the present invention may be provided with a plurality of first wireless apparatuses that perform channel allocation in sequence from the highest priority, and a plurality of second wireless apparatuses that perform channel allocation in response to change channel requests from at least one of the plurality of first wireless apparatuses.

If a plurality of first wireless apparatuses and a plurality of second wireless apparatuses are provided, and the plurality of first wireless apparatuses allocates channels sequentially and then the plurality of second wireless apparatuses allocates channels in response to change channel requests from at least one of the plurality of first wireless apparatuses, the plurality of wireless apparatuses that constitute the wireless network will not allocate channels in parallel.

Moreover, in the preceding description, the wireless apparatuses 31-55 were disposed in a mesh format but the invention is not limited thereto, and the wireless apparatuses 31 -55 may be disposed in any format.

Moreover, in the preceding description, the numbers of network interfaces were two but the invention is not limited thereto, and three or more interfaces may be employed, and two or more are generally acceptable. In such cases, one channel is allocated to one network interface, The number of channels need not necessarily be identical with the number of network interfaces. In the invention, wireless apparatuses 36-40, 42, 44, 46-50 constitute a 'relay wireless apparatus group' that relays packets with the minimum necessary number of relays to all the wireless apparatuses 31-55 that constitute the wireless network 100.

Moreover, wireless apparatuses 36-40, 42, 44, 46-50 constitute the 'plurality of firsl wireless apparatuses' and wireless apparatuses 31-35, 41, 43, 45, 51 -55 constitute the 'plurality of second wireless apparatuses'.

Moreover, in the present invention, the CHΛNGE_CHΛN change channel request constitutes the 'channel allocation request'.

The generality of the present invention is not limited Io the mode of implementation disclosed here. The scope of the present invention is the scope disclosed by the Claims for the invention and is not the mode of implementation described above and includes all equivalent variations within the scope and meaning of the Claims.

The grid of the mesh network need not be complete or symmetrical as shown in the example discussed above.

For simplicity, we have assumed here that the first allocation of any wireless apparatuses is made to the first interface N]FI although NIF2 could easily be used.

Claims

Claims defining the invention are as follows:

1. A wireless ad hoc network to perform autonomous channel allocation comprising: a plurality of first wireless apparatuses, in order of priority each operable to initiate and perform channel allocation to one or more neighbouring wireless apparatuses by sending change allocation requests; and a plurality of second wireless apparatuses each operable to perform channel allocation in response to a received channel allocation request from at least one first wireless apparatus.

2. The wireless ad hoc network according to claim 1 , wherein each first wireless is operable to determine their own priority.

3, The wireless ad hoc network according to claim 1 or 2, wherein each second wireless apparatus is operable to perform channel allocation based on the order that the channel allocation requests are received.

4. The wireless ad hoc network according to any one of the preceding claims, wherein each first wireless apparatus is a wireless relay apparatus operable to relay packets within the wireless ad hoc network,

5. The wireless ad hoc network according to any one of the preceding claims, wherein the priority of each first wireless apparatus is based on a random back-off time and each first wireless apparatus initiates channel allocation after the lapse of the random back-ofT time.

6. The wireless ad hoc network according to any one of the preceding claims, wherein the priority of a first wireless apparatus is based on the number of wireless apparatuses that operate to request relaying of packets to the first wireless apparatus.

7. The wireless ad hoc network according to any one of the preceding claims, wherein the priority of a first wireless apparatus is based on the number of neighbouring wireless apparatuses of the first apparatuses that are first wireless apparatuses,

8. Tiic wireless ad hoc network according to any one of the preceding claims, wherein each first wireless apparatus is operable to initiate channel allocation of an available channel of least interference for communication with neighbouring first wireless apparatuses.

9, The wireless ad hoc network according to any one of the preceding claims, wherein each first wireless apparatus is operable to initiate channel allocation of an available channel, other than an available channel of least interference, for communication with second wireless apparatuses that request relaying of packets to the first wireless apparatus.

10, The wireless ad hoc network according to any one of the preceding claims, wherein the first wireless apparatus is further operable to peτfoτm in the same way as a second wireless apparatus.

1 1. The wireless ad hoc network according to any one of the preceding claims, wherein each wireless apparatus has a plurality of interfaces, and allocates different channels to each of the interfaces.

12. The wireless ad hoc network according to any one of preceding claims, wherein each second wireless apparatus is further operable to broadcast an acknowledgement message to neighbouring apparatuses after performing channel allocation.

13. The wireless ad hoe network according to any one of the preceding claims, wherein each second wireless apparatus is further operable to broadcast a non- acknowledgement message to neighbouring apparatuses in response to a received channel allocation request when channel allocation has been completed on all interfaces of the second wireless apparatus.

14. The wireless ad hoc network according to any one of the preceding claims, wherein the first and second wireless apparatuses are operable to perform channel allocation at multiple intervals.

15. The wireless ad hoc network according to any one of the preceding claims, wherein the network is a wireless mesh networks

16. A method of autonomous channel allocation for a wireless ad hoc network, the method comprising the steps of: in ordeτ of priority, a plurality of first wireless apparatuses each initiating and performing channel allocation to one or more neighbouring wireless apparatuses by sending change allocation requests; and a plurality of second wireless apparatuses each performing channel allocation in response to the channel allocation request received from at least one of the first wireless apparatuses.

17. A method for autonomous channel allocation in a wireless ad hoc network at a relaying wireless apparatus having two or more communication interfaces, the method comprising the steps of: waiting a (ime that is based on a priority of the relaying wireless apparatus among other relaying wireless apparatuses of the network; for each communication interface that docs have a channel allocated, allocating an available channel; and sending a channel allocation request to one or more neighbouring wireless apparatuses that communicate with the relaying wireless apparatus using that interface.