2015 | OriginalPaper | Buchkapitel
Station Assignment with Reallocation
verfasst von : Miguel A. Mosteiro, Yulia Rossikova, Prudence W. H. Wong
Erschienen in: Experimental Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study a dynamic allocation problem that arises in various scenarios where mobile clients joining and leaving have to communicate with static stations via radio transmissions. Restrictions are a maximum delay, or laxity, between consecutive client transmissions and a maximum bandwidth that a station can share among its clients. Clients are assigned to stations so that every client transmits under those restrictions. We consider reallocation algorithms, where clients are revealed at its arrival time, the departure time is unknown until they leave, and clients may be reallocated to another station, but at a cost determined by the laxity We present negative results for related previous protocols that motivate the study; we introduce new protocols that expound trade-offs between station usage and reallocation cost; we prove theoretically bounds on our performance metrics; and we show through simulations that, for realistic scenarios, our protocols behave even better than our theoretical guarantees.