Lightweight Economic Models for
Resource Sharing in Wireless Networks
Maria
Kazandjieva and
makazand@mtholyoke.edu mrm@princeton.edu
.
Introduction
Wireless sensor networks
are becoming increasingly widespread in various contexts. For example, sensor
nodes have been deployed on wildlife for tracking purposes [4], and could be
used on vehicles for exchange of traffic information [8]. The nature of sensor
networks introduces several challenges, including limited battery life,
frequent network disconnections, and limited resources. Similar issues arise in
peer-to-peer (P2P) networks where users join the network, request resources,
use them and then leave. In this case, we are not pressed by the
energy-efficiency problem, but we still have to consider the instability of the
network in terms of dis- and reappearing peers. The
ultimate goal in both sensor networks and P2P network is the efficient use of
resources and transmission of data.
The problem we address is that of managing resources in a sensor network.
Similar work has been done on P2P systems in [7]. In their work Turner and Ross
point out that nodes often do not have an incentive to
participate in resource sharing. Therefore they propose an economic market as a
possible motivation; in this market nodes can offer and request resources in
exchange for some monetary value. We take this idea and adapt it to the sensor
network context. In our model there is a universal payment currency and each
node receives the same initial budget. Sensor nodes request resources without
specifying the ”seller” they would like to buy it
from. In a moderately dense network, on many occasions several potential
sellers are available to serve the same request. Consequently, the main focus
of this work is the design and implementation of algorithms for optimal
decision between sellers.
Overall, the
contributions of this work are the following:
• We built a software simulator, Atrium, which mimics
the interactions between nodes in a wireless network. Atrium allows for the
evaluation of node and system behavior.
• We proposed and implemented two algorithms for decision -making when a client
node re quests services from a seller node.
• We investigate both stationary and mobile sensor networks, and we take
advantage of real mobility data gathered by the ZebraNet project [4].
• We achieved an average improvement of 10% over the baseline case in terms of
percentage of completed requests in the system.
The remainder of this
paper is organized as follows. Section 2 discusses some related work. Section 3
presents the software implementation of the Atrium simulator. Section 4
presents the baseline and newly proposed decision algorithms. Section 5
presents our experimental results. Finally, Section 6 presents our conclusions
and future work.
Related Work
Several projects have
suggested the usage of economic models for resource sharing in both sensor and
P2P networks [8] [7] [2] [6]. One of the main benefits of setting up a market
economy is that is provides us with a decentralized control of resources [3].
This is of key significance in wireless networks since it is more efficient and
appropriate than the centralized model.
Most works in the area agree on the basics of such economic models: the
existence of currency and budget allocation, as well as a pricing scheme. The
work in [7] introduces the lightweight currency paradigm in which exchange of
fake money is in the core of the network economy. In [7] peers are allowed to
have their own virtual currencies but it is not clear what the advantage to
that is. Therefore, we prefer to use the simpler scenario where the entire
system has a single currency.
In different scenarios, a resource can be shared either on individual bases or
as part of a combined resource need. For example, [2] proposes a model in which
nodes pay for a combination of resources, needed for the completion of a single
task. Currently our system only considers the case when one specific resource
is requested, but we plan to add the option of having combinational request in
future work.
In terms of pricing, different projects take various approaches. In [1] and [3]
resource prices depend on supply and demand. Therefore nodes gather information
about the popularity of a resource and its availability in the system. Then a
decision is made on how much the given resource costs. In [8], since the
resource in question is information that the seller possesses, the price is
determined based on relevance to the potential buyer. In [2] the auctioning
model is used and potential client nodes determine their bids based on how
important their request is. One common concern missing in all these models is
that of energy. In our work we propose a pricing scheme that adjusts the
resource price based on how much energy the seller has. Intuitively, it is
reasonable that a sensor that has little energy left will demand a higher price
for its services compared to a node which has battery to spare. This pricing
scheme causes the system to have a more balanced usage of nodes and prevents
the fast energy failure of nodes. A similar concept is proposed in [5] where
the price of a service need is directly related to its energy cost.
As mentioned above, [1] and [2] discuss auction schemes as a way for a seller
to choose between buyers. What these works as well as [8] and [7] do not
address is how one client node can pick between different sellers. It is
entirely possible that the same type of resource is offered by several
neighbors and the buyer has to make a choice. In our work we consider the case
of multiple sellers and propose several decision-making schemes.
Implementation
Atrium
is a software simulator implemented in Java. It creates a distributed network
of nodes, where the size of the network and the number of nodes are configurable.
Each node in the simulated system owns one type of
resource, say a radio transmitter. In addition each node begins the experiment
with a budget allocation of 100, full battery, and a rating of 10. Atrium events
are triggered by a trace file and so is mobility. The events that are currently
supported are movement of node, request for resource, battery charge, node
rating calculation, and node resource failure. The simulator processes the list
of events, updating node attributes and keeping statistics about the network’s
performance.
In order to take into account the energy-constrained
environment of wireless sensor networks, we devise a scheme in which resource
prices are adjusted based on energy. When the nodes in the network start
running low energy, they become more valuable and pricing reflects that.
To reward nodes that are reliable and actively
service requests, and to punish nodes that often fail, we have developed an ”e-bay” style rating system. Nodes are judged on the
number of accepted and the number of successfully completed resource requests.
Overall, pricing and rating the two important aspects of Atrium which allow us
to devise
Decision Algorithms
Since the main question we want to answer with
this project is, What would be a good way to
decide between several potential seller nodes offering the same resource? we propose two different decision schemes. Using Atrium we
were able to test the two algorithms and compare them to a baseline one. We
conduct separate experiments for stationary and mobile sensor networks. Below
we describe the three decision schemes.
Baseline Algorithm
In the baseline algorithm, a client node that is
requesting resources always chooses the seller node with the lowest ID. This
ensures that the decision scheme is completely oblivious to any characteristics
that might differentiate potential sellers. An alternative scheme that might be
used as a baseline is random choice of seller.
Price-Only Algorithm
Exploring the economic idea that cheap goods will
allow for greater purchasing power, we devised an algorithm in which nodes
always pick the resource seller with the lowest price. Intuitively this is a
reasonable choice because spending less money on each transaction in the system
will allow nodes to complete a greater number of transactions. We predict that
such an algorithm will perform very well in systems where cheap nodes have high
availability. Unfortunately, the likelihood of operating in such a network is
low, since quality usually comes at a greater price. A network where low-priced
nodes have high rates of failure will cause the price-only algorithm to perform
badly.
Judging from real life economic models,
we would expect networks of nodes where quality comes at a higher cost. For
this reason we propose a scheme that takes into account not only the price of a
resource but also the quality rating of the seller offering the resource.
Price/Rating
Algorithm
In this algorithm we consider both the resource
price and the overall rating of the seller node. The intuition behind this is
that a rich node is willing to pay more for quality service. Therefore as a
node’s budget changes we assign different weights for the price and rating
components. As the wealth of a client
node increases, the importance of price decreases. On the other hand, if a node
is running low on currency, then it is willing to sacrifice quality of
transaction and pay an affordable price.
Results and Observations
This section presents our experimental results. We
compare the baseline, price-only, and prince/rating schemes in both the
stationary and mobile network domains. For the latter we use two mobility
models:
In a stationary wireless network, applying a non-baseline
algorithm for selection of resource sellers improves the performance
dramatically. (Figure 1) In many cases the system successfully completes 20%
more resource requests compared to the baseline decision scheme. Therefore, the
adaptive decision making (both price-only and price/rating schemes) allows for
efficient and balanced resource usage.
Figure 1
In both versions of the mobile wireless network (Figures
2 and 3), the baseline algorithm underperforms
compared to its more intelligent counterparts. But the difference is small
compared to the stationary case. The difference between baseline and
intelligent algorithms is not as drastic for several reasons:
* mobility helps the baseline algorithm by shuffling nodes around
* mobility often causes clients to be in range of fewer potential sellers
* mobility breaks communication between cooperating nodes
For stationary wireless sensor network, employing
a scheme for selecting sellers increases the overall ability of the network to
share its limited resources. When movement is added to the equation, behavior of
nodes is more unpredictable and therefore there are more factors to be
considered. We believe that more refined price formation models are needed in
order for the price-only and price/rating schemes to be differentiated.
Figure
2 Figure
3
One discovery that we made during the run of our
experiments is that adding a simple seller cache decreases the energy overhead
for the system. We let nodes in the network to keep track of the last three
successful client-seller transactions; then, when a new resource is requested,
the client node first attempts to negotiate with sellers it has used before. If
that fails, the client node would go thought the normal process of querying
neighbors and choosing the best seller, but if it succeeds when using the
cache, then some overhead energy is saved. Figure 4 below represents our cache
results.
Figure
4
Conclusion
This paper has presented the implementation of
Atrium, a software simulator used to investigate resource sharing algorithms.
We have also introduced two schemes for choosing between sellers offering the
same resource. We have showed that a careful consideration of both node’s
quality and price performs better than a baseline scheme. In the work leading
to our final results we also developed an ”e-bay” style node rating scheme, as
well as a cache system for decreasing energy usage.
Acknowledgements
This work was supported by the CRA-W Distribute Mentor Project.
References
[1] R. Buyya, D. Abramson, J.
Giddy, and H. Stockinger. Economic
models for resource management and scheduling in grid computing, 2002.
[2] B. Chun, P. Buonadonna, A. AuYoung,
C. Ng, D. Parkes, J. Shneidman,
A. Snoeren, and A. Vahdat.
Mirage: A microeconomic resource allocation system for sensornet
testbeds, 2005.
[3] D.
[4] P. Juang, H. Oki, Y. Wang, M. Martonosi,
L. Peh, and D. Rubenstein. Energy-efficient computing for
wildlife tracking: Design tradeoffs and early experiences with zebranet. In ASPLOS,
[5] C. Saraydar, N. Mandayam, and D. Goodman. Efficient power control via pricing in wireless data networks, 2002.
[6] V. Siris, B. Briscoe, and D. Songhurst. Economic model for
resource control in wireless networks, 2002.
[7] David A. Turner and Keith W. Ross. A lightweight currency paradigm for the P2P resource market, 2003.
[8] O. Wolfson, B. Xu, and A. P. Sistla. An economic model for resource exchange in mobile peer to peer
networks. In SSDBM, 2004.
[9] B. Xu, A. Ouksel,
and O. Wolfson. Opportunistic
resource exchange in inter-vehicle ad hoc netowrks.
In MDM 2004, January.