Spectrum and medium access allocation for fairness

Each node or link of an ad hoc network assists in the distributed allocation of a data channel to increase fairness, even in a multi-hop network, by tracking a measure of link weight for itself and sharing this information over a control channel with neighboring nodes. The metric can be provided over a dedicated control channel, added as a header to data communication on a data channel, or inferred by monitoring data traffic from the neighboring node. The link weight can be adjusted by a link quality factor based on provided or inferred metrics such as transmission rates, ratio of transmission errors, idle time, etc. For multiple flow queues at a subject node, one with a higher transmission rate can be selected for increased fairness. When a packet is received, medium access includes allocating bandwidth, including bonding multiple frequencies that are determined to be available to both nodes.

BACKGROUND

Wireless communication technology has gained widespread acceptance in recent years. A wireless local access network (WLAN) is a data transmission system to provide location independent network access between computing devices by using radio waves rather than a cable infrastructure. Often, WLANs are implemented as the final link between existing wired network and a group of client computers, giving these users wireless access to the full resources and services of the corporate network across a building or campus setting.

Wireless local area networks have come into greater use, with the advent of the IEEE 802.11 standard. The rate at which wireless networks are being deployed is accelerating along with their size and ubiquity. Wireless networks using access points based on IEEE standard 802.11, commonly referred erroneously to as WiFi comprise a majority of current wireless deployments. The 802.11 standards were implemented to provide reliable and secure wireless connectivity at high data rates. Like all of the IEEE 802 standards, 802.11 standards focus on the bottom two level of the International Organization for Standardization (ISO) model, the physical layer and the data link layer. The data link layer provides and functional and procedural means to transfer data between network entities and to detect and possibly correct errors that may occur in the physical layer. In the current context, this data link layer is further subdivided into Media Access Control (MAC) sublayer that manages interaction of devices with a shared medium. Above the MAC sublayer is the media-independent IEEE 802.2 Logical Link Control (LLC) sublayer that deals with addressing and multiplexing on multi-access media.

Wireless transmissions by hosts within proximity of each other can interfere. Therefore, several medium access control (MAC) protocols for wireless networks have been proposed in the past. In general, MAC protocols may be divided into two types: In centralized protocols, a designated host (often referred to as base station or access point) coordinates access to the wireless medium. A node wanting to transmit must wait until permission to transmit is granted by the coordinator node. The mechanisms for requesting and granting such permission may differ in different protocols. Point Coordination Function (PCF) in IEEE 802.11 is an example of the centralized approach.

In distributed protocols, a coordinator is not needed to arbitrate access to the wireless medium. For instance, in the CSMA (carrier sense multiple access) protocol, a node wishing to transmit a packet does so only if it does not hear another on-going transmission. CSMA protocol is fully distributed, since each node independently determines whether to transmit a packet or not. Distributed Coordination Function (DCF) in IEEE 802.11 is an example of the distributed approach.

There are several benefits of using a distributed approach as compared to a centralized approach: In the centralized approach, if a node cannot communicate with the coordinator, then it cannot transmit any packets. On the other hand, with a distributed protocol, if a node cannot communicate with some nodes, it may still be able transmit packets to other nodes. In the centralized approach, the coordinator has the responsibility of keeping track of the state information for nodes on the LAN. In distributed protocols, this overhead can be eliminated. In a centralized approach, it is difficult to use a battery-powered node as the coordinator, since the coordinator will fail if the battery runs out. With failure-prone coordinators, other nodes must be able to reliably detect failure of the coordinator, and elect a new coordinator.

Challenges exist, however, in implementing a distributed allocation of bandwidth in an ad hoc network not having the benefit of a coordinator. Most of the MAC schemes do not result in optimum transmission pattern, which should provide maximum network utilization, when used in multi-hop networks. In order to provide an optimum transmission pattern or structure, the schedule or queue of all active nodes in the entire network should be known. Given the dynamic and distributed nature of ad hoc networks, the information of the entire network is usually unknown before decisions can be made to start accessing the channel.

SUMMARY

The following presents a simplified summary in order to provide a basic understanding of some aspects of the disclosed versions. This summary is not an extensive overview and is intended to neither identify key or critical elements nor delineate the scope of such versions. Its purpose is to present some concepts of the described versions in a simplified form as a prelude to the more detailed description that is presented later.

In accordance with one or more versions and corresponding disclosure thereof, various aspects are described in connection with a method and apparatus for distributed bandwidth allocation among a plurality of wirelessly communicating nodes of an ad hoc network. At least one flow queue is maintained at a subject node. A metric is obtained representing a flow queue maintained by a neighboring node. A link weight is determined for the maintained flow queue. A second link weight is assigned to the flow queue of the neighboring node and communicated to the subject node. Bandwidth is then allocated of the data channel to send a packet from the maintained flow queue based upon the relative difference in the first and second link weights.

In a wireless mesh network, link load is unevenly distributed, and it depends on the traffic matrix and routing decisions. Rather than relying solely on medium access control as is conventional for mesh architectures, cognitive radio capability is taken advantage of in adding a dimension which is a frequency allocation. A cognitive radio can bond several channels together to increase the capacity of a transmission. This bonding scheme improves fairness. It will allocate a larger bandwidth, such as by bonding several channels together, to a node that transports more traffic.

To the accomplishment of the foregoing and related ends, one or more versions comprise the features hereinafter fully described and particularly pointed out in the claims. The following description and the annexed drawings set forth in detail certain illustrative aspects and are indicative of but a few of the various ways in which the principles of the versions may be employed. Other advantages and novel features will become apparent from the following detailed description when considered in conjunction with the drawings and the disclosed versions are intended to include all such aspects and their equivalents.

DETAILED DESCRIPTION

Each node or link of an ad hoc network assists in the distributed allocation of a data channel to increase fairness, even in a multi-hop network, by tracking a measure of link weight for itself and sharing this information over a control channel with neighboring nodes. The metric can be provided over a dedicated control channel, added as a header to data communication on a data channel, or inferred by monitoring data traffic from the neighboring node. The link weight can be adjusted by a link quality factor based on provided or inferred metrics such as transmission rates, ratio of transmission errors, idle time, etc. For multiple flow queues at a subject node, one with a higher transmission rate can be selected for increased fairness. When a packet is received, medium access includes allocating bandwidth, including bonding multiple frequencies that are determined to be available to both nodes.

Various versions will be presented in terms of systems that may include a number of components, modules, and the like. It is to be understood and appreciated that the various systems may include additional components, modules, etc. and/or may not include all of the components, modules, etc. discussed in connection with the figures. A combination of these approaches may also be used. The various versions disclosed herein can be performed on electrical devices including devices that utilize touch screen display technologies and/or mouse-and-keyboard type interfaces. Examples of such devices include computers (desktop and mobile), smart phones, personal digital assistants (PDAs), and other electronic devices both wired and wireless.

Referring initially toFIG. 1, a multi-hop ad hoc network10includes seven nodes that can only communicate with one, two or three neighboring nodes. For clarity, each link depicted is symmetrically two-way. In particular, a Node “A”12forms a link with Node “B”14as depicted16. Node “B” forms a link with a Node “C”18a depicted at20and forms a link with a Node “D”22as depicted at24. Node “D” further forms a link with a Node “E”26as depicted at28. The Node “E”26further forms a link with Node “F”30as depicted at32and forms a link with Node “G”34as depicted at36. It should be appreciated that aspects have application as well to single hop ad hoc networks and that this arrangement is illustrative only.

Node “B”14includes a cognitive multi-hop fairness component40that maintains a flow queue42of packets that are to be sent. A medium contention component44gains access to link16,20,24to transmit the packets. The transmission is advantageously made with awareness of frequencies that are available to both nodes that form the link, as depicted by a data structure at46. Bandwidth is allocated over a proportion of these available frequencies based upon link weight data48for the subject node14as well as the neighboring nodes12,18,22. It should be appreciated that other nodes inFIG. 1can also include the features depicted for Node “B”14.

In particular, inFIG. 2, a depiction of a network frequency versus time allocation of bandwidth50includes a dedicated control channel (“control”) that serves for signaling between nodes, depicted as Nodes “1”, “2” and “3”. Such signaling of status may be initiated in response to a query from a neighboring node or be periodically broadcast for the benefit of nodes that are within reception range. Use of a plurality of data channels, illustrated as Data “1”, “2”, and “3”, is contended for, as depicted by a Node “1” packet on Data “1” and Node “3” on Data “2” and “3” initially. After a back-off time of “B” once Node “2” sees that the data channel is open, Node “2” takes a larger frequency band of Data channels “1”, “2” and “3” to form a channel of “F” bandwidth. It should be appreciated that control of the channel also is a varied in duration as well as frequency in accordance with a link weight of Node “2” relative to the Nodes “1” and “3”.

It should be appreciated with the benefit of the present disclosure that use of control channel is illustrative and that information about neighboring nodes can be determined by data sent via a data channel intended for consumption by another node for purposes of sharing flow rate or similar metric information. Alternatively, metric data can be embedded in a header of data communication. As yet another alternative, a subject node can monitor the data traffic from other nodes in an ad hoc network to calculate or approximate the metrics for neighboring nodes, such as by sensing idle times. The metrics tracked or disseminated can include size of queues for one or more flow queues handled by the particular node, transmission rates per flow queue/node, and/or transmission time between nodes.

InFIG. 3, there is illustrated a schematic block diagram of a communication device100according to one aspect of the subject invention, in which an ad hoc network fairness scheduler102increases the fair use of a wireless data channel by previously coordinating with other communication devices as to link weights and available frequencies and then allocating bandwidth in frequency and duration in accordance with these link weights. The nodes12,14,18,22,26,30,34ofFIG. 1, as well as any other computing devices capable of establishing control and data wireless communication channels according to aspects of the invention may include components as illustrated inFIG. 3. Thus, the communication device100can include a network interface card (NIC)104which allows the communication device100to communicate over a network such as, for example, the wireless ad hoc network10(FIG. 1). A network interface driver106enables interaction between NIC104and other components of the communication device100, such as, for example, an operating system108and a communicating application110, both resident in a memory112of a computing platform114of the communication device100along with the fairness scheduler102. Driver106may be computer-executable instructions encoded in a suitable computer-readable medium, which may include memory components on NIC104or may include memory storing operating system instructions for device100or other suitable memory depicted at112.

NIC104can provide functionality of a receiver and transmitter configured to receive and transmit wireless communications respectively over a transmit antenna118and a receive antenna124. Components included in the receiver and transmitter are controlled by a transceiver controller128. It should be appreciated that certain components may be externally provided over a data port (not shown)). The port can include at least one of Universal Serial Bus (USB) and/or IEEE 1394 serial communications capabilities. Other technologies that can also be employed are, but are not limited to, for example, infrared communication utilizing an infrared data port, Bluetooth™, Wi-Fi, Wi-Max, etc.

Controller128can receive commands from driver106. In some versions, commands for controller128may be generated within components of operating system108, application110, or applications within the fairness scheduler102. For instance, a cognitive radio scanner132can access components of the receiver through driver106to controller128in order to determine available frequencies. Similarly, status information concerning the operation of NIC104can be collected within controller128and passed to driver106or passed through driver106to operating system108or applications110,132. Accordingly, control functions for any of the components within NIC104can be implemented within controller128or may be implemented within driver106, within components of operating system108, or within applications110,132. Accordingly, the aspects of the invention relating to control of components of NIC104may be implemented by configuration of controller128, programming within driver106or software components within operating system108or applications110,132. However, the specific mechanism by which control functions are implemented can be made by any suitable implementation.

To send packets from the communication device100, the packets can be encoded using an Error Control Coding (ECC) component136providing error control coding of any suitable type. For example, the encoding may use a multi-bit error correcting code. In the version illustrated, ECC component136can add a number of error control bits to each packet to be transmitted. The number of error control bits added to a packet may be configurable in response to commands from controller128. Altering the number of bits per packet used for error control coding is a possible adaptation that may be made in NIC104for poor channel conditions. For example, more error control bits can be added in a noisy channel in which frequent errors occur. However, increasing the number of bits used for error correction reduces the percentage of bits used for data transmission.

An encoding component138may implement any suitable encoding according to a data transmission protocol used for wireless communication. Encoding implemented within encoding component138may use a modulation scheme that is configurable based on input from controller128. The modulation scheme used in encoding component138may also be used to adapt to channel conditions. For example, encoding component138may support a range of encoding schemes with a variable number of bits per symbol. To adapt to noisy channels, encoding component138may be controlled to use an encoding scheme with a high number of bits per symbol. Conversely, in a high-quality channel, encoding component112may be controlled to use an encoding scheme with a low number of bits per symbol, thereby increasing the data transmission rate.

The encoded data are then transmitted by a transmitter140at a transmit power level controlled by a transmit “Xmit” power controller142. Transmission may be made via the transmit antennae118. The transmit power level may also be controlled by controller128and may serve as a further mechanism to adapt to channel conditions. For example, in a noisy channel, a higher transmit power may be specified.

Corresponding processing may be performed on received packets. Packets received by the communication device100at the receive antennae124may be processed through a receiver144and then supplied to a received signal strength indicator (RSSI) component146. RSSI may be obtained from a field in a received packet or it may be directly measured from the received wireless signal and then output in any suitable format. RSSI component146may output a signal strength or a signal to noise ratio (SNR) for any desired packets. In the version illustrated, RSSI component146outputs a signal strength indication based on the received signal strength. However, the signal strength indication may be obtained in any suitable way. For example, it can be a field in a packet (e.g., an ACK packet) that contains an SNR value from a corresponding packet measured at the receiver side (e.g., a DATA packet).

The NIC104may include one or more components that decodes a received signal to produce a set of digital values for processing. The received bits may be modified in a forward-error correction (FEC) component148implementing forward-error decoding. In the version illustrated, FEC component148performs an operation that is the inverse of that performed by ECC component136. FEC component148analyzes the received bits, including the error correction bits, and determines the number of bits in error in each received packet. Using an error correction algorithm, FEC component148determines the correct values for each bit that is incorrect and removes the error correction bits. In the version illustrated, FEC component148is coupled to controller128. Accordingly, controller128has access to information concerning the number of errors detected in each received packet. It should also be appreciated that other types of error correction coding and decoding may be utilized by the communication device100.

The FEC component148is coupled to a received data processing component150which further processes the received packets. Received processing component150may perform any number of received processing operations. For example, received processing component150may include a buffer in which a received packet is stored until it is transferred for further processing within operating system108.

In the version illustrated, network interface card104may be implemented using technology as is known for constructing wireless network interface cards, including implementation of known antennae technology. Likewise, the error correcting coding implemented by ECC component136and FEC component148may be performed according to a known error correction algorithm. Likewise, the encoding performed in encoding component138may be performed in accordance with an 802.11 standard or in any other suitable way. The transmit power may be controlled by transmit power component142also using conventional components. Also, the received signal strength may be measured in RSSI component146in a conventional way, and receive processing component150may be implemented using conventional components. Controller128may also be implemented using conventional technology. For example, all of the components within NIC104may be implemented in a single integrated circuit chip or in multiple integrated circuit chips using technology currently known for constructing network interface cards.

It should be appreciated with the benefit of the present disclosure that the controller128performs cognitive radio functions in a noninterferring manner with the transmit and receive functions of the NIC104. The scanner132detects and characterizes (e.g., pattern matching, bandwidth, power of frequency spectra, duration) in order to detect network devices and interference emitters. This information can be advantageously tagged with time and location data for historical reference and/or persistent interference adaptation. The available frequencies are stored in a data record153for broadcasting to neighboring nodes and for selecting frequencies for use. The memory112and other portions of the computing platform114communicate across a databus158, such as a rules-based logic component168and an artificial intelligence (AI) component170.

The AI component170can facilitate automating performance of one or more features described herein such as predicting link weights or adaptations for interference emitters such as during a situation in which information for neighboring nodes has become stale. Thus, employing various AI-based schemes can assist in carrying out various aspects thereof. For example, a process for determining a frequency and duration allocation be facilitated via an automatic classifier system and process.

A classifier is a function that maps an input attribute vector, x=(x1, x2, x3, x4, xn), to a class label class(x). A classifier can also output a confidence that the input belongs to a class, that is, f(x)=confidence(class(x)). Such classification can employ a probabilistic and/or statistical-based analysis (e.g., factoring into the analysis utilities and costs) to prognose or infer an action that a user desires to be automatically performed.

A support vector machine (SVM) is an example of a classifier that can be employed. The SVM operates by finding a hypersurface in the space of possible inputs that splits in an optimal way the triggering input events from the non-triggering events. Other classification approaches, including Naïve Bayes, Bayesian networks, decision trees, neural networks, fuzzy logic models, maximum entropy models, etc., can be employed. Classification as used herein also is inclusive of statistical regression that is utilized to develop models of priority.

As will be readily appreciated from the subject specification, the subject invention can employ classifiers that are pre-trained (e.g., via a generic training data from multiple users) as well as methods of reinforcement learning (e.g., via observing user behavior, observing trends, receiving extrinsic information). Thus, the subject invention can be used to automatically learn and perform a number of functions, including but not limited to determining, according to a predetermined criteria, a present and/or target location, location-based data and/or services, when/if to communicate data location-based services, preferences for types of data to exchange, etc.

The rules-based logic component168can also be employed to automate certain functions described or suggested herein. In accordance with this alternate aspect, an implementation scheme (e.g., rule) can be applied to define thresholds, initiate location detection, facilitate communication of location-based services, preferences for types of data to exchange, etc. By way of example, it will be appreciated that the rule-based implementation can automatically define criteria thresholds whereby an analyzer component or processor190can employ the thresholds to allocate bandwidth and/or set of data for adaptation (e.g., diversity configuration). In response thereto, the rule-based implementation can affect determination of wireless network bandwidth allocation and/or services by employing a predefined and/or programmed rule(s) based upon any desired criteria (e.g., inferred knowledge about changes to links of an ad hoc network).

According to some aspects, the communication device100may comprise any type of computerized, communication device. For example, the communication device100may comprise a mobile communication device, such as a wireless and/or cellular telephone. Alternatively, the communication device100may comprises a fixed communication device, such as a Proxy Call/Session Control Function (P-CSCF) server, a network device, a server, a computer workstation, etc. It should be understood that communication device100is not limited to such a described or illustrated devices, but may further include a Personal Digital Assistant (PDA), a two-way text pager, a portable computer having a wired or wireless communication portal, and any type of computer platform having a wired and/or wireless communications portal. Further, the communication device100can be a remote-slave or other similar device, such as remote sensors, remote servers, diagnostic tools, data relays, and the like, which does not have an end-user thereof, but which simply communicates data across a wireless or wired network. In alternate aspects, the communication device100may be a wired communication device, such as a landline telephone, personal computer, set-top box or the like. Additionally, it should be noted that any combination of any number of communication devices100of a single type or a plurality of the afore-mentioned types may be utilized in the cellular communication system (not shown). Therefore, the present apparatus and methods can accordingly be performed on any form of wired or wireless device or computer module, including a wired or wireless communication portal, including without limitation, wireless modems, Personal Computer Memory Card International Association (PCMCIA) cards, access terminals, personal computers, telephones, or any combination or sub-combination thereof.

Additionally, the communication device100may include a user interface184for purposes such as requesting, interacting with, and/or playing media content. This user interface184includes an input device186operable to generate or receive a user input into the communication device100, and an output device188operable to generate and/or present information for consumption by the user of the communication device100. For example, input device186may include at least one device such as a keypad and/or keyboard, a mouse, a touch-screen display, a microphone in association with a voice recognition module, etc. In certain aspects, input device186may provide for user input of a request for content or for user input of a request for additional information. Further, for example, output device188may include a display, an audio speaker, a haptic feedback mechanism, etc. Output device188may generate a graphical user interface, a sound, a feeling such as a vibration, etc., and such outputs may be associated, for example, with the presentation of media content.

The computer platform114of the communication device is operable to execute applications to provide functionality to the device100, and which may further interact with input device186and output device188. The memory112of the computer platform114may include volatile and nonvolatile memory portions, such as read-only and/or random-access memory (RAM and ROM), erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM), flash memory, and/or any memory common to computer platforms. Further, memory112may include active memory and storage memory, including an electronic file system and any secondary and/or tertiary storage device, such as magnetic media, optical media, tape, soft and/or hard disk, and removable memory components. In the illustrative version, memory112is depicted as RAM memory with storage device180representing nonvolatile local storage, which can be removeable, each connected to the data bus158of the computer platform114. Certain of the capabilities of the communication device100can be facilitated by code loaded from local storage (not shown), retained in memory112, and executed by a processor190, such as the operating system (OS)108.

Further, computer platform114may also include the processor190, which may be an application-specific integrated circuit (ASIC), or other chipset, processor, logic circuit, or other data processing device. In some aspects, such as when communication device100comprises a cellular telephone, processor or other logic such as an application specific integration circuit (ASIC) (not shown) may execute an application programming interface (API) layers (not shown) that interfaces with any resident software components, such as voice call, data call, and media-related applications in memory112. Device APIs may be a runtime environment executing on the respective communication device100.

Additionally, processor190may include various processing subsystems192embodied in hardware, firmware, software, and combinations thereof, that enable the functionality of communication device100and the operability of the communication device100on a communications system (not shown). For example, processing subsystems192allow for initiating and maintaining communications, and exchanging data, with other networked devices as well as within and/or among components of communication device100. In one aspect, such as in a cellular telephone, processor190may include one or a combination of processing subsystems192, such as: sound, non-volatile memory, file system, transmit, receive, searcher, layer1, layer2, layer3, main control, remote procedure, handset, power management, diagnostic, digital signal processor, vocoder, messaging, call manager, Bluetooth® system, Bluetooth® LPOS, position determination, position engine, user interface, sleep, data services, security, authentication, USIM/SIM (universal subscriber identity module/subscriber identity module), voice services, graphics, USB (universal serial bus), multimedia such as MPEG (Moving Picture Experts Group) protocol multimedia, GPRS (General Packet Radio Service), short message service (SMS), short voice service (SVS™), web browser, etc. For the disclosed aspects, processing subsystems192of processor190may include any subsystem components that interact with applications executing on computer platform114.

Computer platform114may further include a communications module193with functionality in addition to, or as an alternative to, the NIC104, that enables communications among the various components of communication device100, as well as being operable to exchange control and data communication between the communication device100and the ad hoc network10(FIG. 1), such as by accessing a PHYS component195and a MAC component197. Such a communications module193can be embodied in hardware, firmware, software and/or combinations thereof, and may further include all protocols for use in intra-device and inter-device communications.

It should be appreciated that the communication device100includes provisions for power supply. Power can be provided to the processor190and other components forming the communication device100by an onboard power system (e.g., a battery pack or fuel cell). In the event that the power system fails or becomes disconnected from the device100, a supplemental power source can be employed to provide power to the processor190(and other components and to charge the onboard power system, if a chargeable technology. For example, the alternative power source can facilitate an interface to an external grid connection via a power converter. The processor190of the device100can induce a sleep mode to reduce the current draw upon detection of an anticipated power failure. For example, the wireless control component102can advantageously detect a situation in which no control channel is available, or a negotiated data session is still some time away, and turn of portions of the communication device100in order to conserve stored power and/or to reduce thermal loads.

Each link (e.g., communication device100) in an ad hoc network enhances fairness in bandwidth allocation, even in a multi-hop network, by maintaining link weights based upon traffic information (e.g., number of packets queued per each flow, the total number of queued packets, the total number of queued flows, or a combination of the above, etc.) for neighboring nodes in link weights database199. The device100also maintains one or more flow queues201for packets to be sent and calculates a link weight for itself that is communicated to other devices100via a control channel203. When a link (i.e., device100) has a packet to transmit, it will do so by contending for a medium access of the data channel. One of the parameters of the contention mechanism is the link weight, with higher link weights increasing the chances of a node to access the channel. Once a node (i.e., device100) has gained the access to the channel, it senses the available frequencies via the cognitive radio scanner132. Then, it will select a subset of these frequencies as a function of the link weight (i.e., the higher the weight, the more frequencies are selected) and bond them together. In an illustrative implementation of channel contention and frequency bonding mechanisms, based on 802.11 MAC. Each node100disposes of a back-off counter205. The counter205is decremented whenever a node100senses the medium idle. When the counter205drops to zero (0), a node100transmits a packet. Let wibe the weight of node i. In this particular example we will assume it equals to the total number of packets in i's queue. In general, it may be any function of the number of queued packets for each flow.

If the node's transmission was successful, the node i will set its back-off to a random value Biwhose mean value is ft(wi, wj1, . . . , wjn) where wj1, . . . , wjnare weights of neighboring nodes, learn through a signaling protocol. Typically, ft(wi) is a decreasing function of wi. If the transmission failed, the node i will set its back-off to a random value Biwhose mean value is ft(wi)+B′iwhere B′iis the previous initial value of the back-off counter205.

Each node100in a network10maintains a list of frequencies F available to him in data record153. It also learns the frequencies available to its neighbors through some form of signaling protocol that are also stored in data record153. When node i wants to transmit a packet to node j, it will first find the list of frequencies Fi∩ Ffavailable to both nodes i and j.

Then, the node will randomly select N frequencies from the set of the available ones, such that the probability P(N=n)=Fj(n, wi, wj1, . . . , wjn) depends on the weights of link i and its neighbors. It will announce the selected frequencies to the receiver and other neighbors on the signaling channel, bond them and finally transmit a packet over a channel allocation (data channel)207.

Referring now toFIG. 4, a flow diagram of a methodology400according to an version of the invention is shown. The method is for allocating bandwidth among a plurality of flows sharing a wireless data channel. Each flow can correspond to a node, or a number of nodes, where in the latter instance each flow can correspond to a queue over the nodes. The output link can correspond to a network, such as a local-area network (LAN), a multi-hop network, or a wireless network. In block402, the node cognitively determines the list of frequencies available to the node. The available frequencies may be limited by an interference emitter or by neighboring nodes assigned to use certain channels. Available frequencies could also include bands such as those reserved for television broadcasts that are cognitively determined to be unused and available for data communication. In block404, neighboring nodes broadcast, or are queried to broadcast, frequencies that they have determined are available for their use. The available frequencies can differ depending on the particular neighborhood of a respective node. In block406, a weight for each flow is adaptively determined based on a predetermined criterion. The weights are adaptively determined in that they can vary over time, in a dynamic manner, and are not static or fixed a priori.

In one version, the predetermined criterion is an input rate of data packets at each flow. For example, the input rate may be an input rate at which packets are arriving at or within a flow for transmission over the output link. Where each flow corresponds to a node, the packets may be generated by a different application program at the node. Where a flow corresponds to a number of nodes, the packets may be generated by different nodes.

In this version, adaptively determining a weight for each flow in block400includes determining the input rate for each flow, and adaptively determining the weight for each flow as the input rate multiplied by a normalizing constant. For instance, in one version, the input rate at a given time τ is
r(τ)=(tr(t)+ξL)/τ
where, ξ is a rate-sensitivity constant, r(t) is the input rate at a previous time t, and L is the packet size. The rate-sensitivity constant determines sensitivity of the rate estimate to short-term changes in the arrival pattern. Given the input rate, the weight is
w(τ)=t(τ)/Normalizing factor,
where Normalizing factor is a constant. For instance, in the case of a 2 Mbps (mega-bits per second) network, the maximum achievable throughput can be about 1.3 Mbps, where the packet size L is 512 bytes. Thus, a normalizing factor of 1.3 Mbps can be used. With such a normalizing factor, the weight approximately represents the arrival rate as a fraction or multiple of maximum achievable throughput.

In another version, the predetermined criterion is the queue size of each flow. For example, the queue size can correspond to the number of packets within a queue at a flow awaiting transmission by the queue for transmission over the output link. In this version, adaptively determining a weight for each flow in block406includes estimating the number of packets in the queue of each flow, and adaptively determining the weight for each flow as the number of packets in the queue divided by a maximum number of packets allowed in the flow.

Thus, still describing the version where the queue size for each flow is the predetermined criterion for adaptively changing the weights for the flows, the weight can be determined as
w(τ)=(Average queue size(τ))/(Maximum allowed queue size),
Average queue size(τ) is the number of packets pending in the queue at time τ. Maximum allowed queue size specifies the maximum allowed size of the queue for the flow.

In block406, a portion of the bandwidth of the output link is allocated to each flow, proportional to the weight for each flow. Block406can be used in conjunction with protocols and algorithms used to implement fair scheduling in broadcast environments, in which such weights are typically static or fixed a priori implicitly or explicitly. For example, the weights determined in block406can be used to allocate bandwidth to each flow that passes through the same node as well by tracking the local multiple flows as depicted in block407.

In block408, a packet, for example, a packet of data, is received at the node for transmission there from, through the link or network coupling all the nodes, or from an application running on the node. In block409, the local flow with high transmission rate is selected for transmission. In block410, a virtual clock is reset to zero. The virtual clock is a clock maintained by each node within the network. In this version, it is reset only once each time a packet is received. The virtual clock is written as vi(t), where t is actual, physical time—for example, as maintained by a real-time clock within the node—and “i” specifies the node. Thus, the resetting of the virtual clock to zero in block410is written as vi(t)=0.

In block412, the packet is tagged with a start tag. The start tag is a function of the time when the packet arrives at the node. The packet itself is denoted as Pik, where P is the packet, “I” indicates the node, and k indicates the k-th packet received at the node. The tag is specified as Sikand determined as
Sik=max{v(Aik),Fik−1},
where Aikspecifies the real time at which packet Pikarrives at node i, and Fik−1 specifies the finish tag of the previous packet. The finish tag of a packet is determined as
Fik=Sik+γLik/wi,
where Likspecifies the length of the packet and wispecifies weight of node i, higher weight is given to nodes that require a greater share of the bandwidth. γ is the scaling factor used to allow a choice of the scale for the virtual clock.

In block414, the virtual clock is updated. It is noted that the virtual clock is updated only when a packet is transmitted from a node onto the link. Thus, if at time t, a packet is in service, then vi(t) is updated to
vi(t)=max(vi(t),s)
where s is the start tag of the packet in service. It is noted that the virtual clock is not updated at any other time in one version.

Once a node i desires to transmit the packet, then in block416, it determines an appropriate back-off interval, which is generally defined as the length of time the node waits until actually transmitting the packet onto the link. This interval is denoted as Bi, and is based on the start tag and the current virtual time vi(t) in one version. Specifically,
Bi=[η*(Sik−Vi(t))]
where η, the Backoff_Multiplier is a constant in one version.

It is noted that because of the manner in which the start tags and the virtual clock are determined, Biis non-negative. However, if the start tag and the virtual clock are identical, Bimay become equal to zero. To avoid this, in one version, Bi is further modified as
Bi=Bi+Xi
where X is uniformly distributed in [1, β] where β, the Backoff_Window, is a positive integer. This further reduces the probability of back-off intervals of two nodes counting down to zero at the same time, in block416as well the back-off counter is reset to zero after this step is performed.

The node then starts counting from the back-off interval to a predetermined transmission time, such as zero, in block418; that is, the node does not actually send the packet until the predetermined transmission time is reached in block418, as counted down from the back-off interval. Thus, in block420, the node has counted down from the back-off interval to the predetermined transmission time, and therefore transmits the packet over the network or link. At this time, the node also tags the packet with a finish tag, as determined as has been described.

In block422, it listens to determine whether another node has sent a packet at exactly the same time, such that a collision resulted. If not, then the method is done in block424. It is noted that in this case, when another packet needs transmission via the method400ofFIG. 4, that the virtual clock will not be reset in block410, since it is only reset once. However, if a collision has resulted, then a new back-off interval (Bi) must be determined, and the packet ultimately resent. Thus, the method goes back to416. However, in this iteration of416, the back-off counter is increased by one, to indicate that the back-off interval (Bi) has already been determined once, and a new back-off interval is selected, uniformly distributed in
[1,2backoff—counter-1*β],
This new determination of the back-off interval is used if future iterations are necessary—that is, if any more collisions result.

It is noted that this back-off interval is small. This is done to increase the probability that a colliding node “wins” the back-off interval countdown as against the other nodes, so that a collision does not result in unduly delaying the transmission of the packet. However, to minimize the occurrence of too many collisions, the range for Biincreases exponentially with the number of collisions.

It is noted that the specific determination of the back-off interval for a node is not limited to the description above. Other variations are possible, in particular, to trade off between the probability that a collision may occur, and the overhead incurred by the choice of large back-off intervals. In varying versions, two alternatives are determining the back-off interval can be used:

(1) Initially selecting a back-off interval to be linearly proportional to (start tag minus virtual time). In one version, a random component is added to this value. For example, the back-off interval is selected to be uniformly distributed within 20% of (start tag minus virtual time). Such an approach is advantageous when the likelihood of many nodes choosing the same back-off interval is large.

(2) As described in (1), once the back-off interval is chosen, it is decremented until it reaches the predetermined transmission time, in one version, zero. A new back-off interval is not selected for a packet unless a collision occurs when its back-off interval reaches the predetermined transmission time. This approach works because the back-off interval is chosen to be linearly proportional to (start tag minus virtual time). However, where there are many nodes, there can be a case where all nodes choose large back-off intervals, such that too much time is spent idling when the back-off counters are decrementing to the predetermined transmission time. Thus, another alternative is to use a non-linear function to set the back-off interval, but emulate the relative order of back-off intervals chosen in (1). For example, a function of the form K1*(1−K2−(start—tag-virtual—time)) is used in one version. In this case, however, after each packet transmission, the back-off counter of each pending packet needs to be predetermined, so as to emulate the scheme in 1).

The method ofFIG. 4can be summarized as follows. Each node of the network may have a pending packet to be transmitted over the network. For each node that does, when the packet actually arrived at the node—for example, when the packet was generated within the node, and then “arrived” at the node for transmission by a medium access controller (MAC) of the node—the packet is stamped with a start tag, and a back-off interval is determined for the node. The nodes thus start counting down from their respective back-off intervals to zero, in one version. The first node that “wins”—the first node that counts down to zero—sends its packet. This node then is able to receive another packet, and the process starts over for that node. Thus, as nodes count down to zero, they fire off their packets. The method also takes care of the situation where more than one node count down to zero at the same time, which results in a collision.

InFIG. 5, a methodology500provides for obtaining metrics for neighboring nodes for determining link weights begins in block502by an ongoing process of monitoring nodes that comprise an ad hoc network. Those nodes that can be directly or indirectly sensed tend to change with time due to mobility, reception, or being activated for use. Moreover, the amount of communication changes with time even for nodes that continue to sensed. The methodology500addresses three illustrative ways for obtaining metrics for neighboring nodes, which can be occurring simultaneously given that a mix of nodes may comport to different standards and capabilities. In block504, a determination is made as to whether a control channel is available with a neighboring node. If so, the flow metrics can be advantageously provided without tracking or computational burdens nor without burdening the data channels. The flow metrics for determining the link weight for the neighboring node are received and stored, as depicted in block506.

If in block504the control channel was not available, then in block508a further determination is made as to whether the neighboring node is encoding the flow metrics in a message in the data channel. For example, the metric data can be embedded in a header of other data transmissions. While placing a certain transmission overhead on the data channel, this overhead is offset by increased fairness and the computational burden on other nodes to infer the situation of this node. Thus, if present, the flow metric data is stored in block506. If not provided by the neighboring node in block508, then the subject nodes evaluates tracked flow rates of the neighboring node in block510to infer a flow metric and stores the value in block506. The link weight can be based solely on this information.

In the illustrative aspect, the metrics obtained also support adjusting link weights to recognize quality measurements rather than being based solely on the difference in flow queues between two nodes to recognize a quality measurement. For clarity, these additional metrics are assumed to be included with the flow metrics discussed above. However, some metrics could be provided by neighboring nodes either via the control channel or the data channel whereas others may have to be inferred. For instance, a subject node could track the number of transmission failures and resends in order to infer a rate of transmission failure. For example, consider that a link weight “w” for a link “l” is based on a queue size difference between a source node “src” and a destination node “dst”:
w(l)=(q(src(l))−q(dst(l)))*R(l) where (q(src(l))−q(dst(l))),
adjusting the link weight for link “l” by a link quality measurement “R” can provide a more optimized solution in some scenarios. The link quality measurement can be based solely or in combination upon measurements such as transmission rate, fraction of loss packets, expected transmission time, etc. The link quality measurement can be determined by channel or averaged over all channels.

The utility of a link quality measurement can be illustrated. Consider an example with one link connecting very distant nodes, and one link connecting nearby nodes. The link connecting the very distant nodes will have low throughput, even if you assign all available channels to it. Due to its low throughput, the queue at the source will build up, and its weight will be very high. The second link will be unjustly starved. Multiplying the difference in the queue lengths with a link quality (i.e., the shorter link has much better quality) may remedy the situation.

Thus, in block512, an evaluation is done on the tracked link quality measures (e.g., error rate, transmission rate, transmission time, etc.) that are provided by or inferred from neighboring nodes. A determination is made in block514as to whether the information is available for a particular channel. If not, in block516, the link quality factor is based on averaged channel measurements. If so, in block518a link quality factor is assigned per channel. Alternatively, the determination can be made to average in all instances, even when data is available for each channel, such as to address changes in the ad hoc network with new channels becoming available.

With reference toFIG. 6, an exemplary environment910for implementing various aspects of the invention includes a computer912. The computer912includes a processing unit914, a system memory916, and a system bus918. The system bus918couples system components including, but not limited to, the system memory916to the processing unit914. The processing unit914can be any of various available processors. Dual microprocessors and other multiprocessor architectures also can be employed as the processing unit914.

The system memory916includes volatile memory920and nonvolatile memory922. The basic input/output system (BIOS), containing the basic routines to transfer information between elements within the computer912, such as during start-up, is stored in nonvolatile memory922. By way of illustration, and not limitation, nonvolatile memory922can include read only memory (ROM), programmable ROM (PROM), electrically programmable ROM (EPROM), electrically erasable ROM (EEPROM), or flash memory. Volatile memory920includes random access memory (RAM), which acts as external cache memory. By way of illustration and not limitation, RAM is available in many forms such as synchronous RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double data rate SDRAM (DDR SDRAM), enhanced SDRAM (ESDRAM), Synchlink DRAM (SLDRAM), and direct Rambus RAM (DRRAM).

Computer912also includes removable/non-removable, volatile/non-volatile computer storage media.FIG. 6illustrates, for example a disk storage924. Disk storage924includes, but is not limited to, devices like a magnetic disk drive, floppy disk drive, tape drive, Jaz drive, Zip drive, LS-100 drive, flash memory card, or memory stick. In addition, disk storage924can include storage media separately or in combination with other storage media including, but not limited to, an optical disk drive such as a compact disk ROM device (CD-ROM), CD recordable drive (CD-R Drive), CD rewritable drive (CD-RW Drive) or a digital versatile disk ROM drive (DVD-ROM). To facilitate connection of the disk storage devices924to the system bus918, a removable or non-removable interface is typically used such as interface926.

It is to be appreciated thatFIG. 6describes software that acts as an intermediary between users and the basic computer resources described in suitable operating environment910. Such software includes an operating system928. Operating system928, which can be stored on disk storage924, acts to control and allocate resources of the computer system912. System applications930take advantage of the management of resources by operating system928through program modules932and program data934stored either in system memory916or on disk storage924. It is to be appreciated that the subject invention can be implemented with various operating systems or combinations of operating systems.

A user enters commands or information into the computer912through input device(s)936. Input devices936include, but are not limited to, a pointing device such as a mouse, trackball, stylus, touch pad, keyboard, microphone, joystick, game pad, satellite dish, scanner, TV tuner card, digital camera, digital video camera, web camera, and the like. These and other input devices connect to the processing unit914through the system bus918via interface port(s)938. Interface port(s)938include, for example, a serial port, a parallel port, a game port, and a universal serial bus (USB). Output device(s)940use some of the same type of ports as input device(s)936. Thus, for example, a USB port may be used to provide input to computer912, and to output information from computer912to an output device940. Output adapter942is provided to illustrate that there are some output devices940like monitors, speakers, and printers, among other output devices940, that require special adapters. The output adapters942include, by way of illustration and not limitation, video and sound cards that provide a means of connection between the output device940and the system bus918. It should be noted that other devices and/or systems of devices provide both input and output capabilities such as remote computer(s)944.

Computer912can operate in a networked environment using logical connections to one or more remote computers, such as remote computer(s)944. The remote computer(s)944can be a personal computer, a server, a router, a network PC, a workstation, a microprocessor based appliance, a peer device or other common network node and the like, and typically includes many or all of the elements described relative to computer912. For purposes of brevity, only a memory storage device946is illustrated with remote computer(s)944. Remote computer(s)944is logically connected to computer912through a network interface948and then physically connected via communication connection950. Network interface948encompasses communication networks such as local-area networks (LAN) and wide-area networks (WAN). LAN technologies include Fiber Distributed Data Interface (FDDI), Copper Distributed Data Interface (CDDI), Ethernet/IEEE 802.3, Token Ring/IEEE 802.5 and the like. WAN technologies include, but are not limited to, point-to-point links, circuit switching networks like Integrated Services Digital Networks (ISDN) and variations thereon, packet switching networks, and Digital Subscriber Lines (DSL).

Communication connection(s)950refers to the hardware/software employed to connect the network interface948to the bus918. While communication connection950is shown for illustrative clarity inside computer912, it can also be external to computer912. The hardware/software necessary for connection to the network interface948includes, for exemplary purposes only, internal and external technologies such as, modems including regular telephone grade modems, cable modems and DSL modems, ISDN adapters, and Ethernet cards.

FIG. 6is a schematic block diagram of a sample computing environment1000with which the subject invention can interact. The system1000includes one or more client(s)1010. The client(s)1010can be hardware and/or software (e.g., threads, processes, computing devices). The system1000also includes one or more server(s)1030. The server(s)1030can also be hardware and/or software (e.g., threads, processes, computing devices). The servers1030can house threads to perform transformations by employing the subject invention, for example. One possible communication between a client1010and a server1030may be in the form of a data packet adapted to be transmitted between two or more computer processes. The system1000includes a communication framework1050that can be employed to facilitate communications between the client(s)1010and the server(s)1030. The client(s)1010are operably connected to one or more client data store(s)1060that can be employed to store information local to the client(s)1010. Similarly, the server(s)1030are operably connected to one or more server data store(s)1040that can be employed to store information local to the servers1030.