12.1 Spectrum Shortage

Over the past decade, the total demand in the United States for wireless services has approximately doubled annually. Although that trend is slowing (with 60% growth forecast for 2014), growth is still expected to be strong for the next several years [1]. This growing demand for wireless services is creating the so-called “spectrum shortage,” which the United States is starting to address through its National Broadband Plan. In short, the demand for information too often exceeds the capacity of wireless networks to deliver it. In major markets, this phenomenon is already affecting service quality, as users experience reduced data rates because of peak activity.

The growth in demand for wireless services has three main sources. First, the number of network subscribers has been steadily increasing; this is largely due to the popularity of smartphones and tablets, which are continually becoming more powerful and more useful. Second, individual applications are becoming increasingly data intensive; streaming video is the most familiar example and, as video quality improves, becomes more data intensive. Third, the peak density of network subscribers is increasing. In the near future, applications requiring machine-to-machine communication (such as vehicular safety) will materially add to demand. Together, these growth factors are making demand outpace expected service availability in many areas.

The Federal Communication Commission's forecasts project 275 MHz of additional spectrum will be needed to meet demand by 2014 [2]. The shortage will not, of course, be experienced uniformly. While rural areas may not experience substantial quality-of-service (QoS) degradation, urban areas (where the densities of both users and infrastructure are highest) certainly will, especially during times of peak demand. Even now, networks must often cap consumption of wireless services, whether by imposing steep fees for exceeding data plans or simply limiting users’ download speeds. A thorough and current survey of extant methods for reducing congestion is provided by Sen et al. [3]. Networks that can maintain or improve their QoS in the face of this growing demand will have a clear competitive advantage.

Numerous solutions have been proposed and implemented to increase network capacity and address the imminent spectrum shortage. One class of solutions istechnological, which includes developing wireless standards with faster data rates, such as the recent IEEE 802.11ac. Another involves more efficient ownership. Many usage rights are owned by firms with no near-term prospects of actually using them; networks with an urgent need for additional usage rights might buy them to expand capacity. Researchers have also proposed methods to flatten peak demand by incentivizing delayed network activity [4, 5]. Our solution is a novel network architecture and incentive program to encourage use of peer-to-peer (P2P) networking to expand the capacity of cellular networks.

Our model, in essence, provides a relief valve for congestion in cellular networks. When cellular networks are congested, they can subcontract a set of P2P networks to manage some of their load. Each P2P network will consist of multiple WiFi base stations, each governing network traffic in its vicinity. We envision that not all nodes will be within direct communication range of a base station, so the P2P network will require participants to act cooperatively—forwarding network traffic for others. Participation incentives will be offered to join the P2P network rather than remaining in the congested cellular network and may be adjusted to reflect differing participation, increasing for nodes that relay network traffic for other nodes and decreasing for nodes that consume a larger fraction of the P2P network's capacity. Additional incentives may be offered to encourage more continuous participation (and longer-term data caching), as opposed to nodes only remaining in the P2P network while they are actively requesting information. The roles and incentives of this hybrid network architecture are given in Table 12.1.

Currently, cellular network subscription plans typically allow users to switch between 3G/4G and WiFi networks, the incentive for users being that using the WiFi network does not deplete the subscriber's minutes or data plan, as applicable. The differences between our proposed hybrid network and extant commercial models are

• cellular network selection of P2P participants,
• incentive distribution for P2P network participation,
• multi-hop access to WiFi base stations (rather than only direct communication),
• automatic activity-driven incentive adjustments in the P2P network.

Managing this hybrid network to maximize profitability will entail solving multiple optimization problems, which we address in the following sections of this chapter. What participation level should the P2P network seek? Given the need for multi-hop communication between nodes and the base station, the P2P network will need sufficient density to enable continuous routing paths. However, although some additional density will be desirable as a safety margin (for when nodes exit the P2P network), additional participation may provide little value. Thus, the optimal network density is slightly higher than the minimum sufficient density. How should participants be incentivized to achieve the optimal density, especially given that willingness to participate will differ according to location, time, and other factors? And, finally, what contextual information needs to be gathered to support these decisions in dynamic environments?

We present our model from a bottom-up perspective, introducing its components and underlying concepts before explaining how they operate together. Before introducing our optimization model, the next three sections will cover

• P2P networking,
• commercial viability,
• Self-Balancing Supply/Demand (SBSD)protocol.

12.2 Peer-To-Peer Networking

The defining characteristic of P2P networking is the equality of network participants. In client–server models, all communication progresses up and down the network hierarchy. For example, a message sent from one client to another is not transmitted directly but must be sent up to a server and then down to the destination client. In contrast, the network architecture and node roles are more flexible in P2P models; nodes typically act as routers for their peers (other nodes in the network) and forward network traffic for them. In fact, any node in a P2P network may function as a client or server in regard to a particular query or response—provided, of course, that it has the requested information and that the nodes have common protocols to regulate their interactions. Compared to traditional client–server models, P2P offers some important advantages:

• Load Sharing. The decentralized structure of P2P networks enables better load sharing, because network traffic does not have to always be routed through a centralized server. Better predictive caching models (placing information near likely query sources) support improved load sharing.
• Faster Response Time. By decentralizing network traffic, each peer server may only need to respond to relatively few queries even under heavy total network traffic. Consequently, response time can be faster. This is especially important for multi-hop routing in wireless ad hoc networks, where the communication medium must be shared among potentially large node groups.
• Minimal Oversight. Typically, P2P applications require minimal oversight, because they do not rely on the continuous operation and availability of centralized servers. The loss of a server node will not disable the network.

Although our concern is wireless networking, the principles of P2P models apply to both wired and wireless networks. For wired networks, the music sharing application Napster is a well-known early P2P model, although in fact it was supported by centralized servers. In Napster's P2P model, users would register their available files at one of Napster's servers, where other users were able to search for content. The actual file transfer, however, occurred directly between the two users in question. Other more recent P2P applications, such as Freenet (www.freenet.net), operate entirely without such centralized server support.

As far as wireless networks, P2P models have been proposed and implemented for numerous uses; although somewhat dated, Akyildiz and Wang [6] provides a good introduction to their basic practical issues. Of particular interest are situational awareness applications, where groups of nodes share their knowledge about contextual variables, such as the location, mobility, density, and activity of groups of nodes. Many such applications (e.g., vehicular safety by sharing real-time mobility data) rely on all nodes gathering and forwarding continuous updates on variables of interest. These applications naturally conform to P2P models when contextual data is not sent to or obtained from centralized locations. Situational awareness applications can rely on networks of static or mobile nodes, with somewhat different characteristics in practice for each.

When nodes are static, data is typically gathered continuously by sensor nodes and directed to one or more data sinks. Most often, the data sinks may simply store the data (e.g., in remotely deployed environmental monitoring networks) or intermittently forward batches of data outside the sensor network (to respond to queries or provide real-time updates to network users). In some cases, however, the information might be used by the sensor nodes themselves (e.g., cross-checking observed variables as a means to detect observation errors or defective sensors).

For networks of mobile nodes, similar concerns arise. Mobile node groups may elect data sinks or interface with fixed infrastructure points. Compared to static topologies, the fluidity of such networks tends to make reliance on direct communication between nodes more advisable. Routing data to sinks can impose delays that degrade the value of continuous updates. For some applications, such as suggesting travel routes, moderate delays may be acceptable. Other applications, such as vehicular safety, may be extremely time sensitive. For those, pure P2P models are a natural and promising approach. Although P2P computing has numerous uses, it also presents a number of challenges not present in client–server models, especially for multi-hop wireless networking.

• Free Riding. P2P networking for multi-hop wireless networks requires that users forward traffic for others. Policies must be implemented to make free riding (using the P2P service without forwarding traffic for others) infeasible, essentially by making free access contingent on providing services to other nodes. Other nodes will either have their network access restricted or be charged for it.
• Weaker Network Security. Wireless networks are inherently less secure than wired networks, as any transmission can be overheard by nearby nodes. Depending on the nature of the communication protocol and messages, security concerns may include not only eavesdropping but even the proper operation of the communication model.
• User Density Requirements. In order to route packets quickly, multi-hop wireless routing requires sufficient node density to build complete end-to-end routes without waiting for nodes to move into mutual communication range. The variety of potential P2P transmission ranges can, of course, allow for varying densities over a route. However, as the maximum data rate is generally higher for shorter transmission ranges, higher density should allow greater P2P network throughput.
• Encouraging Participation. User density provides an upper bound on the number of potential P2P network participants. Not all of them are likely to be willing to forward network traffic for other users. Yet the presence of more willing users will tend to drive down the cost of establishing a given P2P network density.

12.3 Commercial Viability

In order to apply P2P as a support mechanism for cellular networks, the system must be commercially viable. That is, the network company must recoup any expenses associated with providing and monitoring the P2P service. Although a great deal of research has been directed toward technical issues of P2P schemes, the relevant economic considerations have been largely ignored. The basic economic issues have been briefly covered in Reference [7], although little beyond recognizing that they exist as open research problems.

We advocate a voluntary participation model, where the network compensates cooperative P2P behaviors in the form of additional usage rights or reduced subscription charges. Extant research, such as Reference [8], suggests that wireless network subscribers are generally willing to modify their network usage in accordance with incentive programs, even if the incentives are small. The core economic question is what performance improvements can be obtained at what cost to the network provider. The P2P network can provide additional network capacity, but the end result of this extra capacity may take different forms depending on the network provider's strategic goals, such as the following.

• More Data per User. The most direct use of the additional capacity is to simply increase monthly data plans across the board for all users.
• Increased Subscription Revenues. A network might keep its existing subscription plans in place and use the additional capacity for promotions to attract new customers.
• Driving Down Operating Costs. Network providers will need to continuously add capacity in order to keep up with growing demand for wireless services. However, adopting P2P models can delay the need for such expansions, with consequent lower operating costs.

These basic principles of P2P system goals are easily understood but do not address the crucial question of participation pricing. That is, what compensation should be offered to attract the needed P2P participation density? Not so low as to fail to form a useful P2P network but not so high as to bring in many more nodes than those required. This efficiency problem becomes more difficult in dynamic wireless environments, where nodes may move rapidly, participate intermittently, and so on. Ideally, the network would also monitor the popularity of queries to drive data caching decisions. To achieve that, network providers need to continuously monitor node density, the popularity of queries, and the persistence of nodes in the network.

While the cellular network is congested, the P2P network will operate continuously in parallel with it. To ensure its continuous operation, incentives must be paid out to encourage cooperative behaviors among nodes. This gives rise to two fundamental questions that must be answered. First, what total incentives will be distributed to the P2P network participants; that is, how much will it cost to create and maintain it? Second, how will those incentives be distributed to the individual participants?

In general, we would assume an increasing asymptotic function for the total value of the set of participating nodes over any given time period. This implies a decreasing and approximately hyperbolic function for the value of each individual node's participation. Further, assuming nodes have variable willingness to participate, increasing the node density will reduce the cost of obtaining a given number of participants. The exact function parameters will, of course, vary across different networks but its general shape will be known. Importantly, however, when node density is high in the cellular network, the costs of creating the P2P network will be relatively low.

The next question is devising functions that describe this model. Here, there are analogues with congestion pricing in transportation. In those models, such as Nie [9], the goal is inducing a sufficient number of drivers to leave the roads to achieve a system optimal set of travel times. In a real-time environment, this can be achieved by requiring payment of tolls and, in principle, accruing additional payments to drivers that are not on the road. Applying this type of model to our proposed P2P network requires a slightly different framework.

Instead of charging drivers to remain on the roads, we would approach the problem strictly from an incentivization standpoint. That is, because network users already pay subscription fees, there is no need to levy additional charges. Instead, theP2P network functions to support the cellular network, and so participation (to enable gathering state information as well as actually forwarding packets for other nodes) would be rewarded. The incentives distributed to create the P2P network can be obtained as a prorated share of subscription fees for the congested periods. Because these incentives will be distributed according to individual nodes’ assistance in creating the network, the P2P network can function entirely on a compensated voluntary basis.

We can formulate the costs of maintaining the P2P network as follows. Assume that n users wish to use the cellular network that can only support c users at the desired QoS. Assume also that each of the n users has paid k_i to use the cellular network during interval i. Then, the users above the cellular network's capacity can provide over interval i. This quantity must be shared with the P2P network participants, whose share in interval i we indicate by . There will remain the quantity to be kept by the cellular and P2P network providers.

Although the above model serves to illustrate how the P2P network will be funded, multiple practical refinements suggest themselves. First, the users may be insufficient (or indeed too numerous) to form a P2P network with adequate QoS. Second, the cellular network provider will wish to minimize ω_i within each interval in order to maximize profitability, while maintaining adequate QoS in both the P2P and cellular networks. Lastly, the size of the interval i is important; finer granularity will enable faster response to changing network conditions, potentially enhancing both profitability and QoS.

In order to set appropriate incentives in dynamic environments, the network provider must continuously gather smart pricing information (SPI). This information can then be leveraged to enhance routing performance (in terms of packet delivery ratio and latency). The key difference between the cellular network and the P2P network is that the cellular network can reasonably ensure access to any requested information, while the P2P network only allows access to information cached at participating nodes and then only probabilistically. So, it is imperative for the P2P network to not only provide complete routing paths but also to cache information likely to be requested by nearby nodes.

The P2P network requires estimates of the following.

• Demand for Information. It is a well-known fact that information is often requested by multiple users. In fact, this is essential to Google's caching functions, where more popular pages are kept more accessible. Applications with a geographic component (such as travel assistance) are especially likely to have coocated demand. On the other hand, it is also true that unique or highly infrequent requests should not be retained in the P2P network, as their likelihood of reuse is small.
• Required Incentives. We expect that users will largely rely on pricing assistance software to set their participation threshold. That is because few users would wish to constantly monitor such microtransactions. These automated assistants will inform the network provider, at the very least, about which price offers are accepted and which are rejected. Combined with data about time and participation density, this information will support estimating participation as a function of incentive price.
• Predictive Caching. To place information near likely queries, it is necessary to gather information about the locations of query sources. Then, participating nodes can cache information in accordance with estimated future demand. This will both reduce the communication costs of searching for information (i.e., a smaller set of nodes can be searched) and of obtaining it (because routing paths will be shorter).

12.4 Self-Balancing Supply/Demand

Our SBSD protocol is a paradigm for demand-driven information search and discovery. Unlike point-to-point routing protocols [such as Ad Hoc On-Demand Distance Vector (AODV) and Dynamic Source Routing (DSR)], which focus narrowly on constructing routing paths between known pairs of nodes, SBSD combines dynamic controlled flooding with predictive caching [10]. Our SBSD's predictive caching model and medium access control functions encompass the SPI requirements for our proposed P2P network model.

Flooding-based routing performs well in high mobility environments, where message destinations are very often unknown and any routes between them are ephemeral. Further, when multiple nodes request the same information, flooding can enable substantially faster responses to network users by widely caching popular information. This is a sensible approach when query sources do not know the query's destination and when multiple nodes often request the same information.

The basic SBSD model strives to flood query packets (and any matching responses found) in the vicinity of their sources. The depth of a given query's flooding depends on its popularity (how many other nodes have posted the same query) relative to others nearby. All else equal, the size of the flooding area is approximately a linear function of the frequency of demand. SBSD also controls the persistence of information according to a spatiotemporal utility function (given in the next paragraph). Packets closer in time and distance to their sources will be retained longer.

Each node will retain a queue of queries and responses to be retained untilexpiration (or perhaps discarded in the unlikely event of memory storage being overloaded). The items in this queue are ranked according to the utility function:

where u is the item's utility, a is its age (the time since the item was created or most recently requested), h is the hop count (the number of hops traversed en route to its location), and f is its frequency (the number of unique users interested in the item, either posting the same query or receiving the same response).

The utility-based ranking is used to enable autonomous node decisions to create predictable group behaviors. Each node individually estimates the set of high utility items it will be able to forward during their remaining times to live. This estimation creates a forwarding threshold. Items with sufficiently high utility are forwarded until their utility declines below the threshold (primarily due to aging without compensating demand increases). The low utility items are simply cached until expiration, unless new demand for them boosts their frequency or resets their age. As most nearby copies of an item will have similar utility values, an item's flooding area tends to expand to a predictable flooding depth given a locally known arrival rate for new items.

Our utility function provides the important result of creating a linear relationship between an item's popular and its total contribution to network congestion during its lifetime [11]. That is, more popular items are granted a proportionally greater consumption of network resources. The above utility function approximates the negative ratio between the network congestion an item will ultimately be allowed to create and how much it has already created. That is, as an item's flooding proceeds, the transmissions of its copies add more to network congestion, which lowers the utility of creating new copies in the network. Further, this ratio's approximation is made without incurring the communication overhead to calculate either item separately.

We have developed a number of extensions to our SBSD protocol enabling more efficient delivery than provided through flooding. In a variety of ways, these extensions reduce the prevalence of redundant transmissions (where recipients have already received a copy of a transmitted packet). They can be applied to increase search depth for queries, propagation depth for response data, additional transmissions for more reliable delivery, or combinations thereof. The most recent of these extensions, Reference [12], considers geographically constrained flooding areas for vehicular networking in order to boost network throughput.

The SBSD model provides a means to obtain the following essential data, which may be delivered intermittently in batches or via sampling to the network provider.

• What Information Is Popular? Highly skewed demands for information are seen in many domains. Although somewhat dated, Reference [13] for example, analyzed a large search engine log (of a billion searches) and found that the most popular 25 queries accounted for 1.5% of search activity. Streaming video is another case, where the most popular videos can accumulate hundreds of millions of views while many videos struggle to reach a few thousand.
• Where Is It Popular? In terms of predictive caching for the P2P network, it is vital to know the corelation between popularity and location. If, for example, two users want the same information but are miles apart, multi-hop routing is probably not a good approach. However, many situational awareness applications tend to naturally provide users with information that is closely correlated with location. Vehicular safety and travel information are good examples, as many cars in an area will need the same information about nearby vehicles and travel routes.
• Node Density, Topology, and Mobility. In order to estimate the participation requirements for the P2P network, the network provider must know an approximate distribution of the node population. The alternative would be to learn this on the fly, which naturally adds an extra layer of delay to the P2P network. That is, if node density is insufficient, that fact has to be learned before incentives can be offered to boost density.
• Willingness to Participate. The set of nodes in a given area will be known to the cellular network. From their past participation history, the cellular network will be able to estimate what incentives are necessary to ensure sufficient cooperation to achieve performance targets. Such estimates may be further refined by considering node density and cellular network congestion

12.5 Hybrid Network Model Overview

Our proposed model [14] will regulate load sharing in the hybrid cellular–P2P network. When the cellular network becomes congested, it will release a portion of itscustomers and assign them to the P2P network. The goal is that all users will receive better QoS than in the congested cellular network. The customers who remain in the cellular network will benefit from the reduced congestion level, while those added to the P2P network will receive QoS at least equal to what they would have obtained if they remained in the congested cellular network. As customers enter and leave the networks, they will need to be assigned to one network or the other. Ultimately, when the cellular network's congestion is sufficiently low, all customers in the P2P network will resume using the cellular network.

Our intention is to implement our model without disrupting the cellular network's existing methods of operation. Instead, our model will seamlessly add capacity to the cellular network through a system of voluntary, incentivized participation. Rather than attempt to dynamically adjust incentives to current needs, the cellular network will assign nodes to the P2P network with indeterminate future incentives. Implementing this model will require coordinating organizational, algorithmic, hardware, distributed accounting, and security elements.

12.6 Incentive Modeling

Our proposed P2P incentive model was inspired by our earlier work in modeling congestion management and vehicular pollution in the transportation domain [15]. The similarities between transportation and wireless networking are clear: in both, individual users of a shared resource (whether a set of roads or the wireless communication medium) impose negative externalities on other users. The basis of our solution is a Pigouvian tax model in which users are charged according to their negative externalities in order to arrive at a socially optimal consumption of the shared resource.

In the transportation domain, traffic congestion is primarily relieved by charging tolls (to directly reduce the number of vehicles on the road, either by inducing them to take less congested routes, switch modes, or not drive during congested times). Related models have been developed to support searches and dynamic pricing for parking spaces, which can also suffer from congestion when demand exceeds supply [16]. Likewise, packet routing can be modeled as a set of data flows between sources and destinations and network congestion as a cost that rises with the volume of data the network handles.

For our P2P network, we wish to minimize network congestion primarily through autonomous node decisions. This is accomplished through a pair of models both of which offer users trade-offs between their individual QoS and their earned incentives. The first is a flow model that estimates the P2P network congestion generated by a given set of nodes and their generated network traffic. The second is aprioritization model, where some network traffic may be delayed during congested periods; this is analogous to charging tolls for faster travel routes or paying some vehicles to park during peak traffic. In both cases, users have the option to receive improved QoS by accepting a smaller quantity of incentives.

12.7 Flow Model

Our flow model represents the P2P network as a graph of vertices and edges, in which data flows are managed to maintain congestion below an acceptable level determined by the cellular network. Each vertex represents a nonnull set of participating mobile devices and each edge represents a link between such groups of mobile devices. Depending on the granularity desired, nodes at a given vertex might all be in mutual communication range or be more dispersed. Edges represent direct communication links between at least one pair of nodes from adjacent vertices. Data flows over edges; when network traffic is heavier, the flows become slower.

Consider a graph network , with a set V of vertices and a set E of edges.

• For an edge , let x_e be its network traffic and be the time required to traverse e, where we assume is a nonnegative, strictly increasing, and convex function. Because our SBSD model uses controlled flooding, we adopt a first-order approximation of modeling network traffic as uniform across all edges in E.
• The planning horizon is M periods. For precise management, the planning horizon may be divided into an arbitrarily large number of periods but which will entail additional computational costs and more frequent information gathering about network topology and congestion. On the other hand, if peak network traffic is sufficiently uniform, it might be sufficient to simply set M=1, that is, a single-period planning horizon.
• Let R and S, respectively, denote the sets of origin and destination nodes. The amount of network traffic to be routed from any to any is represented by .
• The set of paths connecting an origin–destination pair rs is denotedby , and during a period m, the flow on path is represented by .
• The P2P network participation incentives are equally shared among all participating nodes and are depleted as nodes contribute to network congestion. Nodes are permitted to purchase additional congestion rights from other nodes. Let the unit price of buying additional congestion rights for period m through the competitive bidding process be multiplied by a transaction cost factor .
• Let denote the congestion (i.e., the delay on all other network traffic) inflicted by network traffic x on edge e in period . Following our assumption that increases with x, is a nonnegative, strictly increasing, and convex function.
• Let be the maximum network congestion permitted in a period m; the maximum congestion permitted over the entire planning horizon is .
• Each node in the P2P network is granted the right to inflict an average amount of congestion by injecting new network traffic. Let be the cost of assigning the congestion rights over the planning horizon. As this communication will further increase network traffic, the function is a nonnegative, strictly increasing, and convex.

We formulate the equilibrium problem with network congestion costs as

Input Data. , where and .

Decision Variables. , where , and .

The above model extends [17], a single-period pollution credit trading model with a known total pollution cap and no transaction costs. Setting our model parameters as , , and , and using a known constant , our model reduces to the one from [17]. Our model is feasible, similar to the simpler classical traffic assignment problem, and contains features needed to consider the broader impacts of network congestion policies, which are needed to guard against unintended consequences of policy decisions. The following are few examples.

1. Variable Period and Horizon Caps. Letting change allows analyzing the consequences of dynamic congestion caps, such as for peak and off-peak loads. The overall cap may also be changed. During many periods, no monitoring may be needed, for example, for light network traffic typical of late evening and early morning. Variable horizon caps allow considering transitions across temporal monitoring boundaries.
2. Realistic Congestion Levels. Congestion is not a simple linear function of node density but is affected by node behaviors, network topology, and sources of interference from outside the P2P network. The pollution constraint represented by is a nonnegative, strictly increasing, and convex function; it does not assume linearity.
3. Moving Beyond Simple Linear Relationships. Including congestion rights in the objective function lets us explicitly incorporate the effect of congestion rights on optimal flows in our analysis. This is particularly necessary for systems with many monitoring points, which increases system complexity.
4. Cellular Network Involvement. The model determines the optimal congestion cap but the cellular network might select a different congestion cap to achieve other goals, such as operating the P2P network to reach particular performance targets. The model also informs system planners what costs are required toimpose a range of potential congestion cap distributions.

Incentive models can yield unintended consequences. As shown in Reference [18], price discrimination across different types of network traffic sometimes benefits the network provider at the expense of customers, sometimes the opposite, and in some cases benefits both. To better understand the likely consequences of network policy decisions, our flow model might be further developed to consider the following factors more deeply.

1. Balancing Congestion. To balance congestion across cellular and P2P components of the hybrid network, the congestion target for the P2P network must match that of the cellular network. However, the P2P network has the additional constraint of requiring a minimum node density to provide continuous routing paths.
2. Graph Modeling. The grouping of P2P network nodes into vertices is a necessary abstraction for our model; treating each node as a vertex would continuously require an enormous amount of communication to track network topology. However, the abstraction leads to difficult modeling questions. How many nodes should a vertex contain? What area should those nodes occupy? How many hops should traverse a vertex? One solution is for the cellular network may specifically select nodes that are densely located on or near major roads. This will simultaneously address P2P node density concerns while conforming to the link-based transportation model assumptions.
3. Density Modeling. In transportation models, vehicle density converts almost directly to traffic density. There might be some large trucks and buses that take up additional space but, typically, they compose a small fraction of total vehicular traffic. For wireless networking, however, it is important to distinguish between individual nodes. Individual node contributions to traffic can vary far greater than vehicle sizes (e.g., compare a customer watching streaming video vs one intermittently loading web pages).
4. Monitored Variables. Pollution in the transportation model corresponds to the network congestion produced by each node. The impact of congestion will be felt differently in the cellular and P2P networks. That is, in the cellular network, assuming a constant per-node network traffic quantity, congestion rises linearly with the node population governed by a given cell tower. In the P2P network, however, the benefits of node population initially outweigh the likely costs of congestion.
5. Predictive Congestion Cap. As congestion in the P2P network increases, somenetwork traffic will simply expire before it reaches its destination. In terms of congestion management, it would be better for nodes to post their queries in subsequent periods. For such cases, a sensible policy would be to enforce delays on additional traffic for which congestion rights cannot be bought from other network participants.
6. Intermittent Node Participation. To improve the model's accuracy, the length of each period should be less than the typical duration of P2P participation. This will allow better assessments of incentive requirements and needs for new participations but will require additional tracking of nodes. Given those facts, the cellular network might opt instead to provide additional incentives for nodes willing to participate across multiple periods.

12.8 Prioritization Model

We have also formulated low overhead approaches to regulating P2P network traffic in terms of autonomous forwarding decisions by individual nodes. That is, how do nodes prioritize network traffic without exacerbating congestion by adding many new rounds of communication? When the P2P network is congested, the participation incentives can be adjusted according to the willingness of nodes to accept delays on their communications. While maintaining the same total incentives for the entire P2P network, nodes that accept such delays will obtain a share of participation incentives from other nodes.

We enable nodes to rank traffic through another utility model, this one reflecting the external costs of network congestion. Broadly, nodes accumulate incentives by forwarding network traffic for other nodes and may consume incentives by injecting their own traffic into the P2P network. Like our previous model for route assignments, this model is also inspired from the transportation domain with the goal of jointly capping vehicular pollution and congestion [16]. In that paper, models were presented for cases where tradable pollution credits were either divisible or indivisible, that is, a seller's supply of pollution credits would be sold either in whole or not at all. For example, a driver who elected to delay travel until congestion was relieved might prefer to sell his/her entire stock of credits. In this networking domain, it may likewise happen that transactions involve some of all of the node's participation incentives.

12.8.1 Divisible Incentives

In this case, each P2P network user will choose a priority level from a range of options offered by the network provider. According to the priority level chosen, a node's traffic will be more or less delayed, which will transfer credits from the high priority users to the low priority ones. As needed, nodes may purchase quantities of credits from other users or, in the absence of nearby sellers, from the P2P network provider.

Transactions are not actively conducted by individual nodes, nor are they necessarily chosen to maximize incentive accumulation for particular nodes. Instead, our model will rank potential transactions with a combination of individual node profit and awareness of a transaction's effect on network congestion, according to the utility function for a trade g between a seller i and a buyer j as follows:

where is a step function (equal to 1 for and 0 otherwise), is the reduction in network congestion from accepting a forwarding delay, and is a parameter expressing buyer preferences (for a trade between a seller i and a buyer , . A buyer with will prefer the lowest price seller from among those whose congestion costs exceed a floor . In other words, buyer j prefers matches with high consumption of P2P network capacity. Without the loss of generality, the floor can be set to 0. A buyer with 1 will select the seller with the highest congestion contribution, so long as the seller i ceases initiating any new communications within the P2P network (which it no longer could, having sold all its incentives to buyer .

The model makes several assumptions. Notably, it explicitly considers the possibility that a seller may sell all his/her credits. This may not actually happen in the above formulation; the sale may be partial, in which case, buyer j is simply overestimating the value of its matching with seller i. As a result, this may lead to a suboptimal solution or unfeasibility. A compensating parameter that encourages transactions that relieve network congestion is introduced to favor sellers with smaller supplies of pollution credits to sell.

Utility is highest when either (i) P2P network usage pricing maximizes the pricedifferential between buyer and seller, that is, a lower selling price increases utility, or (ii) the incentive depletion rate is high, making network usage more expensive, then demand for incentives will rise and sellers will ask higher prices for theirs. These two cases suggest the existence of price equilibria between sellers and buyers. Setting arbitrarily high seller prices and low buyer prices will not promote trading. The utility function, therefore, encapsulates the market incentives for network users to either participate solely by assisting peers or use the network at shorter more expensive intervals by purchasing incentives at increasing prices.

12.8.2 Indivisible Incentives

When most transactions involve fully depleting a user's incentives, the assumption of indivisibility is a reasonable approximation. For example, many users in the P2P network might elect to participate only in order to earn the participation incentives. In that case, they might sell their credits immediately upon joining (or leaving) the P2P network. Alternatively, there might be a small number of very heavy network users who wish to buy large quantities of incentives from their peers. The case of indivisible incentives uses a slightly different utility function than the one given earlier for divisible incentives:

where differs only in step function . Here the utility is higher if the transaction results in a seller surrendering all its incentives and thus ceasing to contribute to network congestion.

In both the divisible and indivisible models, the objective of transactions is to maximize the system utility. As the utility expresses the best matching for the whole system in terms of achieving network congestion relief, it must adjust prices in order to achieve system goals. That is, transactions must optimize congestion relief for all the partitions of set S of sellers. For each partition , the best match between the elements of partition (which are disjoint subsets of S covering and the buyers must be found so the total utility isoptimal.

The aggregate utility of a set of matches can be computed in several ways and will determine whether the individual buyers and sellers are optimally matched. The complexity of the problem is NP-hard in both the divisible and indivisible formulations [19]. Note that not all partitions need to be considered. A partition is said to be feasible if at least one element can be matched to one buyer. Further, let be the congestion contributed by seller i. Assume seller i has been matched to a buyer j. In other words, there exists a unique element of , that has been matched to buyer j and contains seller i. We say that a partition is relevant if the set of transactions does not result in exceeding the system-wide congestion cap determined to provide adequate QoS.

12.9 Conclusion

Currently, both cellular and WiFi networks are ubiquitous in urban areas. The WiFi networks may be underutilized during peak cellular network usage, because of difficulties in joining or remaining in a WiFi network. This is especially true for highly mobile network users for which direct communication with infrastructure is infeasible. The problem is creating a framework for enabling the cellular network to shift some of its network load to a set of WiFi networks, thereby relieving congestion in the cellular network while offering adequate QoS to the nodes removed from it.

In this chapter, we have presented our model for a hybrid cellular–P2P network, which was inspired by our earlier work in modeling congestion management and vehicular pollution in the transportation domain. The similarities between transportation and wireless networking are clear: in both, individual users of a shared resource (whether a set of roads or the wireless communication medium) impose negative externalities on other users. The basis of our solution is a Pigouvian tax model, in which users are charged according to their negative externalities in order to arrive at a socially optimal consumption of the shared resource.

During times when the cellular network is congested, a set of P2P networks will be created to increase the entire system's capacity. Although the cellular network will select nodes to join the P2P network, they will have the option to decline (and remain in the congested cellular network). However, remaining nodes that agree to participate in the P2P network will be incentivized for their assistance in forwarding other nodes’ network traffic. These incentives will be paid out from subscription fees, thus allowing P2P network participants to partially recoup their costs of cellular network usage in return for expanding its capacity.

References

1. 1. PricewaterhouseCoopers LLC, Real time: The growing demand for data—2012 North American wireless industry survey, 2013.
2. 2. Federal Communications Commission, Mobile broadband: the benefits of additional spectrum, October 2010.
3. 3. S. Sen, C. Joe-Wong, S. Ha, and M. Chiang, “A survey of smart data pricing: Past proposals, current plans, and future trends,” ACM Computing Surveys, 46(2), 2014.
4. 4. S. Ha, S. Sen, C. Joe-Wong, Y. Im, and M. Chiang, “TUBE: time-dependent pricing for mobile data,” Proceedings of SIGCOMM’12, Helsinki, Finland, pp. 247–258, Aug. 2012.
5. 5. P. Loiseau, G. Schwartz, J. Musacchio, S. Amin, and S. Sastry, “Incentive Mechanisms for Internet Congestion Management: Fixed-Budget Rebate Versus Time-of-Day Pricing,” IEEE/ACM Transactions on Networks, 22(2), 2013, 647–661.
6. 6. I. Akyildiz and X. Wang, “A survey on wireless mesh networks,” IEEE Radio Communications, 2005, s23–s30.
7. 7. Z. Wan, “Commercial issues in hybrid cellular ad-hoc networks,” IEEE 2011 Conference on Management of E-commerce and E-governance, Shanghai, China, 2011.
8. 8. J. Dyaberi, B. Parsons, K. Kannan, V. Pai, Y. Chen, R. Jana, D. Stern, A. Varshavsky, and B. Wei, “Managing cellular congestion using incentives,” IEEE Communications Magazine, 50(11), 2012, 100–107.
9. 9. Y. Nie, “Transaction costs and tradable mobility credits,” Transportation Research Part B: Methodological, 46(1), 2012, 189–203.
10. 10. A. Ouksel and D. Lundquist, “Demand-driven publish/subscribe in mobile environments,” Wireless Networks,16(8), 2010, 2237–2261.
11. 11. D. Lundquist, A Context-Aware Paradigm for Information Discovery and Dissemination in Mobile Environments, Advisor: Aris Ouksel, University of Illinois at Chicago, Chicago, IL, 2011.
12. 12. A. Ouksel and D. Lundquist, “A context-aware cross-layer broadcast model for ad hoc networks,” Personal and Ubiquitous Computing, 18(4), 2014, 851–864.
13. 13. C. Silverstein, H. Marais, M. Henzinger, and M. Moricz, “Analysis of a very large web search engine query log,” ACM Special Interest Group on Information Retrieval, 33(1), 1999, 6–12.
14. 14. A. Ouksel and D. Lundquist, “DF100: CACL: A context-aware cross-layer broadcast scheduling scheme,” Provisional UIC patent, 2012.
15. 15. A. M. Ouksel and T. Lee, Public Policy Implications of Cap and Trade of Pollution Credits and Switching of Travel Modes Incentives, University of Illinois: CISORS Technical Report #5, 2011.
16. 16. A. Ouksel, Pollution Measurements and Pollution Maps, University of Illinois: CISORS Technical Report #12, 2011.
17. 17. H. Yang and X. Wang, “Managing network mobility with tradable credits,” Transportation Research Part B: Methodological, 45(3), 2011, 580–594.
18. 18. A. Lahiri, R. Dewan, and M. Freimer, “Pricing of Wireless Services: Service Pricing vs. Traffic Pricing,” Information Systems Research, 24(2), 2013, 418–435.
19. 19. C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, Inc., New Jersey, 1982.