TY - GEN
T1 - Station assignment with applications to sensing
AU - Fernández Anta, Antonio
AU - Kowalski, Dariusz R.
AU - Mosteiro, Miguel A.
AU - Wong, Prudence W.H.
N1 - Funding Information:
This work was supported in part by the Comunidad de Madrid (S2009TIC-1692), the Spanish MICINN/MINECO (TEC2011-29688-C02-01), the National Natural Science Foundation of China (61020106002), the National Science Foundation (CCF-0937829, CCF-1114930), and Kean University UFRI grant.
PY - 2013
Y1 - 2013
N2 - We study an allocation problem that arises in various scenarios. For instance, a health monitoring system where ambulatory patients carry sensors that must periodically upload physiological data. Another example is participatory sensing, where communities of mobile device users upload periodically information about their environment. We assume that devices or sensors (generically called clients) join and leave the system continuously, and they must upload/download data to static devices (or base stations), via radio transmissions. The mobility of clients, the limited range of transmission, and the possibly ephemeral nature of the clients are modeled by characterizing each client with a life interval and a stations group, so that different clients may or may not coincide in time and/or stations to connect. The intrinsically shared nature of the access to base stations is modeled by introducing a maximum station bandwidth that is shared among its connected clients, a client laxity, which bounds the maximum time that an active client is not transmitting to some base station, and a client bandwidth, which bounds the minimum bandwidth that a client requires in each transmission. Under the model described, we study the problem of assigning clients to base stations so that every client transmits to some station in its group, limited by laxities and bandwidths. We call this problem the Station Assignment problem. We study the impact of the rate and burstiness of the arrival of clients on the solvability of Station Assignment. To carry out a worst-case analysis we use a typical adversarial methodology: we assume the presence of an adversary that controls the arrival and departure of clients. The adversary is limited by two parameters that model the rate and the burstiness of the stations load (hence, limitting the rate and burstiness of the client arrivals). Specifically, we show upper and lower bounds on the rate and burstiness of the arrival for various client arrival schedules and protocol classes. The problem has connections with Load Balancing and Scheduling, usually studied using competitive analysis. To the best of our knowledge, this is the first time that the Station Assignment problem is studied under adversarial arrivals.
AB - We study an allocation problem that arises in various scenarios. For instance, a health monitoring system where ambulatory patients carry sensors that must periodically upload physiological data. Another example is participatory sensing, where communities of mobile device users upload periodically information about their environment. We assume that devices or sensors (generically called clients) join and leave the system continuously, and they must upload/download data to static devices (or base stations), via radio transmissions. The mobility of clients, the limited range of transmission, and the possibly ephemeral nature of the clients are modeled by characterizing each client with a life interval and a stations group, so that different clients may or may not coincide in time and/or stations to connect. The intrinsically shared nature of the access to base stations is modeled by introducing a maximum station bandwidth that is shared among its connected clients, a client laxity, which bounds the maximum time that an active client is not transmitting to some base station, and a client bandwidth, which bounds the minimum bandwidth that a client requires in each transmission. Under the model described, we study the problem of assigning clients to base stations so that every client transmits to some station in its group, limited by laxities and bandwidths. We call this problem the Station Assignment problem. We study the impact of the rate and burstiness of the arrival of clients on the solvability of Station Assignment. To carry out a worst-case analysis we use a typical adversarial methodology: we assume the presence of an adversary that controls the arrival and departure of clients. The adversary is limited by two parameters that model the rate and the burstiness of the stations load (hence, limitting the rate and burstiness of the client arrivals). Specifically, we show upper and lower bounds on the rate and burstiness of the arrival for various client arrival schedules and protocol classes. The problem has connections with Load Balancing and Scheduling, usually studied using competitive analysis. To the best of our knowledge, this is the first time that the Station Assignment problem is studied under adversarial arrivals.
KW - Continuous adversarial dynamics
KW - Health monitoring systems
KW - Participatory sensing
KW - Periodic sensing
KW - Station Assignment
UR - http://www.scopus.com/inward/record.url?scp=84958233703&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958233703&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45346-5_12
DO - 10.1007/978-3-642-45346-5_12
M3 - Conference contribution
AN - SCOPUS:84958233703
SN - 9783642453458
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 155
EP - 169
BT - Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, Revised Selected Papers
PB - Springer Verlag
T2 - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013
Y2 - 5 September 2013 through 6 September 2013
ER -