VCG with Communities on Random Ad Hoc Networks
We study game-theoretic mechanisms for routing in wireless ad hoc networks. Our major results include a combination of theoretical bounds and extensive simulations, showing that VCG-based routing in wireless ad-hoc networks exhibits small frugality ratio with high probability. Game-theoretic mechani...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2011-05-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2011/895398 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832547282799558656 |
|---|---|
| author | Gunes Ercal Rafit Izhak-Ratzin Rupak Majumdar Adam Meyerson |
| author_facet | Gunes Ercal Rafit Izhak-Ratzin Rupak Majumdar Adam Meyerson |
| author_sort | Gunes Ercal |
| collection | DOAJ |
| description | We study game-theoretic mechanisms for routing in wireless ad hoc networks. Our major results include a combination of theoretical bounds and extensive simulations, showing that VCG-based routing in wireless ad-hoc networks exhibits small frugality ratio with high probability. Game-theoretic mechanisms capture the noncooperative and selfish behavior of nodes in a resource-constrained environment. There have been some recent proposals to use these mechanisms (in particular VCG) for routing in wireless ad-hoc networks, and some frugality bounds are known when the connectivity graph is essentially complete. We are the first to show frugality bounds for random geometric graphs, a well-known model for ad-hoc wireless connectivity. In addition, we generalize the model of agent behavior by allowing sets of nodes to form communities to maximize total profit. We are the first to analyze the performance of VCG under such a community model. While some recent truthful protocols for the traditional (individual) agent model have improved upon the frugality of VCG by selecting paths to minimize not only the cost but the overpayment, we show that extending such protocols to the community model requires solving NP-complete problems which are provably hard to approximate. |
| format | Article |
| id | doaj-art-4faf5f1dd2a64211827ac4dd3cd4bf4b |
| institution | Kabale University |
| issn | 1550-1477 |
| language | English |
| publishDate | 2011-05-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-4faf5f1dd2a64211827ac4dd3cd4bf4b2025-02-03T06:45:23ZengWileyInternational Journal of Distributed Sensor Networks1550-14772011-05-01710.1155/2011/895398895398VCG with Communities on Random Ad Hoc NetworksGunes Ercal0Rafit Izhak-Ratzin1Rupak Majumdar2Adam Meyerson3 University of Kansas, Lawrence, KS 66045, USA Palo Alto Networks, Sunnyvale, CA 94089, USA Max Planck Institute, 66123 Saarbruecken, Germany University of California, Los Angeles, CA 90095, USAWe study game-theoretic mechanisms for routing in wireless ad hoc networks. Our major results include a combination of theoretical bounds and extensive simulations, showing that VCG-based routing in wireless ad-hoc networks exhibits small frugality ratio with high probability. Game-theoretic mechanisms capture the noncooperative and selfish behavior of nodes in a resource-constrained environment. There have been some recent proposals to use these mechanisms (in particular VCG) for routing in wireless ad-hoc networks, and some frugality bounds are known when the connectivity graph is essentially complete. We are the first to show frugality bounds for random geometric graphs, a well-known model for ad-hoc wireless connectivity. In addition, we generalize the model of agent behavior by allowing sets of nodes to form communities to maximize total profit. We are the first to analyze the performance of VCG under such a community model. While some recent truthful protocols for the traditional (individual) agent model have improved upon the frugality of VCG by selecting paths to minimize not only the cost but the overpayment, we show that extending such protocols to the community model requires solving NP-complete problems which are provably hard to approximate.https://doi.org/10.1155/2011/895398 |
| spellingShingle | Gunes Ercal Rafit Izhak-Ratzin Rupak Majumdar Adam Meyerson VCG with Communities on Random Ad Hoc Networks International Journal of Distributed Sensor Networks |
| title | VCG with Communities on Random Ad Hoc Networks |
| title_full | VCG with Communities on Random Ad Hoc Networks |
| title_fullStr | VCG with Communities on Random Ad Hoc Networks |
| title_full_unstemmed | VCG with Communities on Random Ad Hoc Networks |
| title_short | VCG with Communities on Random Ad Hoc Networks |
| title_sort | vcg with communities on random ad hoc networks |
| url | https://doi.org/10.1155/2011/895398 |
| work_keys_str_mv | AT gunesercal vcgwithcommunitiesonrandomadhocnetworks AT rafitizhakratzin vcgwithcommunitiesonrandomadhocnetworks AT rupakmajumdar vcgwithcommunitiesonrandomadhocnetworks AT adammeyerson vcgwithcommunitiesonrandomadhocnetworks |