Ad Hoc Networking

Access Control For Ad Hoc Networks

Ad Hoc networks provide communications between nodes, and do not need a preexisting organization of the nodes in order for the network to work. A particular feature of many ad hoc networks is that they employ a decentralized control architecture for arbitrating access to the shared medium. The prototype for this control is called Collision Sense, Multiple Access (CSMA), which provides that each node listens to the network prior to transmitting, to assure availability of a clear channel. Then, if the channel is clear, it seeks to transmit. If the transmission detects that a collision occurred during transmission, the node waits for an opportunity to retransmit. CSMA protocols tend to perform acceptably up to about 50% of theoretical network capacity, and thereafter degrade rapidly due to collisions and retransmits. As can be seen, CSMA does not rely on action of any central or control node, and therefore is generally tolerant to network restructuring.

Multi hop networks retransmit data in a chain of nodes, allowing an extended range of communications. Multihop networks (MANETs) raise the issues of so-called blind nodes, that is, nodes which cannot communicate directly with each other. In a wired network, for example, all nodes within an unswitched subnet are presumed to be in direct communication with one another. In a multihop network, CSMA is ineffective because an intended target of a communication may be subject to mutual interference between transmissions from nodes which cannot directly sense each other. That is, the "carrier sense" technology cannot be relied upon. Thus, a more complex control paradigm is required. Interactive control schemes typically consume communications bandwidth, and therefore must be optimized to avoid undue inefficiency.

One known protocol employs transmission scheduling (e.g., Time Domain Multiple Access or TDMA), which allocates a time division multiplex slot for control over the communications medium for each participant. This, however, requires an a priori definition of the members of the network, and with large memberships, inefficiently allocates slots to nodes which may have no need for access. Another protocol employs a token ring, which requires each node to expressly defer access to the network to a subsequent node. This scheme is relatively intolerant to architectural modifications. Another scheme arbitrates access "fairly", that is, the protocol allows each node to request access, which is then granted proportionally to the various requestors.

Auction theory permits each node to bid for access to the "scarce resource" based on its own valuation of the opportunity. Two factors typically limit the application of auctions to wireless multihop networks: the need for a central auctioneer, and the fact that the "scarce resource", than is, control over a communications channel, differs for each node, and therefore the subject of the auction is not common between bidders. Likewise, in a dynamically changing network architecture, the network topology may change during the auction and communication realization process.

A significant issue therefore results from non-overlapping communications zones. Each node in an ad hoc network has an antenna coverage pattern. Further, the communications may be asymmetric, that is, the range and pattern of the transmitter may differ from that of a corresponding receiver. A transmitter may therefore cause interference to a receiver of which it is not aware. An agile antenna must be "aimed" at its target for effective use, and the possibility of spatial division multiplexing further complicates the control issues (while creating opportunities for increased efficiency).

Most ad hoc network employ in-channel control, that is, both substantive data communications and arbitration of network access share the same communications channels. This, of course, implies that the control suffers the same limitations as communications. However, since we presume that the control requires less bandwidth and different quality of service than normal communications, this requirement may be unnecessary and inefficient. Therefore, a control architecture is proposed which employs out of band or differently modulated communications for control information. Once this in-band, on channel, limitation is relaxed, it is seen that the control issues are more tractable. For example, the data communications channel may employ a high gain, directional antenna with an effective range of 2 km with an aperture of 15 degrees for communications in excess of 1 MBS. On the other hand, the control channel may employ an omnidirectional antenna with an effective range of 10 km for communications at 32 KBS. Because of the vast range differences, and the further possibility for multihop control networks, a distributed control can be implemented over a relatively complete network segment, to fully and efficiently coordinate data communications. Clearly, in a network which extends over a large geographic area, the distributed control need not be globally aware. Therefore, if one presumes that relevance decreases with some metric of distance, at some point, an estimate of the network state beyond a distance may be substituted for actual knowledge, with low probablistic penalty.

The proposed system employs 802.11x and/or DSRC (Dedicated Short Range Communications, for telematics), using a high gain antenna array for fundamental data communications and GMRS or a low frequency ISM band using an omnidirectional antenna for network control. GPS functionality allows direct communication of position and geography, although this may be inferred by other means. Therefore, geospatial data is available for dynamic network configuration. The high gain antenna array provides spatial selectivity with about 15-30 degree (far field) aperture segments, while the radio is capable of simultaneous communication over 8 channels or bands. A single antenna segment may support multiple frequency channels/bands simultaneously. The antenna is intended for horizontal communications only. Polarization is vertical, although other polarizations (horizontal, circular) may be employed, either due to antenna topology, or to provide further opportunity for channel separation.

While auctions typically employ an auctioneer to evaluate bids and issue final dispositions, a central auctioneer is in fact not a theoretical requirement of an auction. What is required is that the subject of the auction be defined, that each bid be evaluated to determine which bidder wins, and that the winning bidder be informed. In the case of a channel auction, the subject of the auction is freedom from interference for a communication channel for a block of time. The channel is defined both by frequency (or other transmission parameter) and space. For example, each bidder broadcasts its georeferenced channel requirement, along with a valuation therefor (the bid). The bids are then received by all receivers, which overlay the bids as a map. Using a common public algorithm, the receivers then each optimize the value of the map, with each offeror particularly evaluating the value to itself. The offerors then broadcast their resolved valuations for the channels which they seek to accept (with possible ranked acceptances), which are then again mapped, allowing the entire local ad hoc network to agree on a maximum valuation scheme. A further exchange may be performed to resolve ambiguities or inconsistencies, although this is sought to be minimized, since such exchanges may have a negative impact on overall system efficiency. Contended channels may be negotiated directly between offerors and possibly bidders. This later communication may employ either the control channel or data channel. The winning map is then either broadcast or inferred from prior communications, and data communications may then commence, for example during the next time-slot. It is also possible to have non-predetermined communication durations, multiple providers to a single bidder, or other more complex schemes. Ultimately, however, through a regional voting scheme, the network architecture and/or protocol is defined, and may vary over time. Because the control channel has greater range than the communications channels, the likelihood of blind nodes impacting local decisions is low, especially where the network is not heavily loaded. Where the network is highly loaded, extended negotiations may be required to resolve all contests over channel allocation. This negotiation may include negotiation over transmit power, modulation type, antenna pattern, etc.

Directional antennas, with coordinated control for multiple simultaneous communication streams, lead to overall increased community bandwidth, reduced multihop penalty, and potential for significantly extended range if there is sufficient population density of nodes.

In some networks, the channel is used to transmit a response to a database query. That is, the results of the query are unknown to the requestor at the time of request, and typically the quantity or usefulness of the information may also be unknown. Typical auction technologies would require a blind bid, that is, a bidder bidding on an unknown. However, it is also possible to transmit the query as a part of the control sequence. To the extent that the response to the query is local or relatively low cost to the recipient, a test query may be executed to determine the quantity or quality of the complete response. This information may be conveyed to the bidder, also through the control channel, or the information used to determine a bid value from a value function.

In order to allow relevance weighting of previously unknown information, while avoiding unnecessary interactive communication, a bidder must convey a utility function, that is, an implicit statement of the contingent value of the bid. The utility function is then evaluated in context, after communication, to define the bid, thereby permitting knowledge of the auctioneer to supplement knowledge of the bidder to achieve an optimal valuation. Such utility functions, if sufficiently durable, may be retained for an extended period. The broadcast of such a utility function is economically efficient if the auction itself is strategyproof, that is, the optimal strategy for a bidder is to bid its true private value. In cases where this presumption is not available, the utility function may be protected cryptographically, or communicated in a manner which protects the bidder from inappropriate disclosure.

One application of ad hoc networking technology is in the field of telematics, where inter-vehicle communication is employed to convey relevant information. For example, each telematics module includes a GPS, navigational system, and sensor network. An ad hoc, multi-hop wireless communication network allows vehicles to exchange relevant data, and in particular allows a vehicle to receive updated information from other vehicles which have recently traveled the same intended path, or otherwise possess the required information.

In the proposed system, the intended recipient of the communication seeks to control the medium, that is, a channel defined in time, space and frequency, whereas the transmitter conveys value. Prior to the communication, the recipient does not know what information is available, and therefore cannot place, a priori, an accurate value on this information. On the other hand, the transmitter does have knowledge of the communication content. The bidder therefore communicates a utility function, comprising objective and subjective valuation criteria, which are resolved by the transmitter to an economic bid value.

Each contestant for the resource (bidder) broadcasts its own utility function for access to a resource, as a best and final offer. These scheme therefore has characteristics of a sealed bid auction. These broadcast bids are then received by offerors (transmitters) which then use their own knowledge to compute the normalized bid value. As discussed above, the values are used as parameters of a mapping problem, which seeks to maximize the value of the map using a common algorithm, such that all nodes with common information achieve the same map, or nearly so, but for the unresolved valuation issues. Since the control channel covers a wider area than the data communications channel, it is likely that each offeror will have a relatively consistent map for the particular resource in question. The offerors then broadcast and exchange their local resolved bids for resources under their control. Where multiple offerors conflict for the same resource, that with the highest broadcast value controls the resource. Where there are map conflicts, such that offerors have conflicting resources for which there is insufficient information available at each node to resolve the optimum map, further information may be communicated. At some point, "renegotiations" cease, and an arbitrary "fair" rule is applied. The "fair" rules are default, such that in the event of a communications error, the network architecture will be implied based on the prior control communication status.

Where multiple recipients are within reception range (including multihop) for a given auctioneer, and the information is to be broadcast rather than sent over a virtual private network, their combined utilities for the information represent the bid for that respective resource.

"Fairness" is ensured by allocating an economic value to the bid. A bidder is charged, for example, for transmitting the bid, as well as the resolved value of its utility function, or the next lowest bid value (e.g., a Vickrey auction). The bid value is divided between the transmitter and deferred bidders. Each bidder maintains a local economic account from which to bid. This account may be cash-equivalent or synthetic currency. In the later case, each node may receive replenishment of its account based on a vector "distance" from a prior state, for example, time, space, and network topology. At least some of these factors, particularly time and space (itinerary), are predictable by a bidder, and therefore a bidding strategy may be optimized with respect to anticipated replenishment opportunities. In general, so long as the parties and circumstances remain the same, a bidder has a relatively fixed asset base from which to purchase and sell resources, which are adaptively priced based on the auction. As circumstances change, a node account returns to a neutral state. The account value may regress to a mean over time, so that new participants start with a standard pool of resources. Security over accounting is based on known micropayment technologies.

It is noted that the auction itself, and implementation of auction strategies, are fully automated, based on objective and subjective factors which are acquired by the system, generally in advance. For example, the user programs a travel itinerary, with a user profile derived from passive observation over past usage. In adopting a bidding strategy, a bidder seeks to expend a budget of credits to achieve maximum benefit, while retaining sufficient resources within some margin of safety to allow for the probability of emergency or urgent requests. Through historical analysis, the bidding strategy, i.e., the parameters of the communicated utility function, may be tuned.

The system is not particularly intended for voice communications. That is, relatively low bandwidth, high quality of service channels are not the focus of the design. Rather, the design is optimized for high bandwidth packet data links, where interruption, latency, and interference are tolerable. It is indeed possible to communicate voice, for example using a voice over IP protocol (VOIP), although an additional parameter of quality of service, may become important. Typically, existing cellular infrastructure is available near most roads for voice communications, and the cost for use of this infrastructure does not depend on whether the source is mobile or stationary. Thus, since most voice calls will require, at some point, access to the fixed infrastructure, the benefits of mobile ad hoc networking for this application are not clear. On the other hand, if the fixed infrastructure providers are viewed as clients rather than suppliers, significant opportunities exist. The build-out of the cellular networks at present include most of the economically justifiable sites. Therefore, additional build-out, especially in the present economy, is difficult. By using mobile ad hoc networking to extend the reach of the fixed infrastructure, nulls in the coverage pattern may be statistically minimized, without substantial capital investment.