File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1614222.1614232
- Scopus: eid_2-s2.0-70350633646
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Auction-based resource allocation for hierarchical wireless mesh networks in rural areas
Title | Auction-based resource allocation for hierarchical wireless mesh networks in rural areas |
---|---|
Authors | |
Keywords | Auction algorithms IEEE 802.16 Resource allo-cation Wireless mesh networks |
Issue Date | 2009 |
Publisher | Association for Computing Machinery (ACM). |
Citation | The 4th ACM Workshop on Challenged Networks (Mobicom CHANTS 2009), Beijing, China, 25 September 2009. In Proceedings of the 4th ACM Workshop on Challenged networks, 2009 How to Cite? |
Abstract | Hierarchical wireless mesh networks (WMNs), in which multiple layers of mesh routers (MRs) share one centralized gateway, are gaining importance in providing broadband Internet services in rural areas. Such WMNs are effective in that they can provide a wide coverage area in a cost effective manner. However, more often than not, such MRs are owned and operated by different autonomous entities, which might not have the incentive to comply with a central rule. Thus, in such a competitive non-cooperative environment, effective resource allocation is a notoriously difficult problem. In this paper, we propose a novel auction based framework, in which the gateway, equipped with the precious high speed Internet connection, serves as the auctioneer, while the first-level MRs (i.e., those with direct wireless connections to the gateway) act as bidders competing resources among each other. Specifically, a major novelty of our framework is that the valuation and payment functions are derived based on practical considerations and have realistic physical significance. Based on this framework, we first present the Vickrey-Clarke-Groves (VCG) based auction approaches. To further improve performance, we then propose two novel relay auction (RA) algorithms and analyze the effectiveness of their bidding strategies using the game theoretic solution concept of Nash equilibrium (NE). To realize the NE in a practical distributed computing fashion, we also design an iterative bid updating algorithm. Through simulations, we find that the proposed RA algorithms can achieve competitive performance in terms of resource allocation efficiency as the VCG ones, while giving much better connection blocking probability performance, and also having the capability to balance the efficiency and fairness by adjusting the payment function. Copyright 2009 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/126118 |
ISBN | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kong, Z | en_HK |
dc.contributor.author | Kwok, YK | en_HK |
dc.date.accessioned | 2010-10-31T12:10:46Z | - |
dc.date.available | 2010-10-31T12:10:46Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.citation | The 4th ACM Workshop on Challenged Networks (Mobicom CHANTS 2009), Beijing, China, 25 September 2009. In Proceedings of the 4th ACM Workshop on Challenged networks, 2009 | en_HK |
dc.identifier.isbn | 978-1-60558-741-7 | - |
dc.identifier.uri | http://hdl.handle.net/10722/126118 | - |
dc.description.abstract | Hierarchical wireless mesh networks (WMNs), in which multiple layers of mesh routers (MRs) share one centralized gateway, are gaining importance in providing broadband Internet services in rural areas. Such WMNs are effective in that they can provide a wide coverage area in a cost effective manner. However, more often than not, such MRs are owned and operated by different autonomous entities, which might not have the incentive to comply with a central rule. Thus, in such a competitive non-cooperative environment, effective resource allocation is a notoriously difficult problem. In this paper, we propose a novel auction based framework, in which the gateway, equipped with the precious high speed Internet connection, serves as the auctioneer, while the first-level MRs (i.e., those with direct wireless connections to the gateway) act as bidders competing resources among each other. Specifically, a major novelty of our framework is that the valuation and payment functions are derived based on practical considerations and have realistic physical significance. Based on this framework, we first present the Vickrey-Clarke-Groves (VCG) based auction approaches. To further improve performance, we then propose two novel relay auction (RA) algorithms and analyze the effectiveness of their bidding strategies using the game theoretic solution concept of Nash equilibrium (NE). To realize the NE in a practical distributed computing fashion, we also design an iterative bid updating algorithm. Through simulations, we find that the proposed RA algorithms can achieve competitive performance in terms of resource allocation efficiency as the VCG ones, while giving much better connection blocking probability performance, and also having the capability to balance the efficiency and fairness by adjusting the payment function. Copyright 2009 ACM. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Association for Computing Machinery (ACM). | - |
dc.relation.ispartof | Annual International Conference on Mobile Computing and Networking Workshops, MobiCom'09 - Proceedings of the 4th ACM Workshop on Challenged Networks, CHANTS'09 | en_HK |
dc.subject | Auction algorithms | en_HK |
dc.subject | IEEE 802.16 | en_HK |
dc.subject | Resource allo-cation | en_HK |
dc.subject | Wireless mesh networks | en_HK |
dc.title | Auction-based resource allocation for hierarchical wireless mesh networks in rural areas | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Kwok, YK:ykwok@eee.hku.hk | en_HK |
dc.identifier.authority | Kwok, YK=rp00128 | en_HK |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1145/1614222.1614232 | en_HK |
dc.identifier.scopus | eid_2-s2.0-70350633646 | en_HK |
dc.identifier.hkuros | 175081 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-70350633646&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 51 | en_HK |
dc.identifier.epage | 58 | en_HK |
dc.publisher.place | United States | - |
dc.description.other | The 4th ACM Workshop on Challenged Networks (Mobicom CHANTS 2009), Beijing, China, 25 September 2009. In Proceedings of the 4th ACM Workshop on Challenged networks, 2009 | - |
dc.identifier.scopusauthorid | Kong, Z=7006536683 | en_HK |
dc.identifier.scopusauthorid | Kwok, YK=7101857718 | en_HK |