OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Kim, E-S.; Glass, C. (2015)
Publisher: Elsevier
Journal: European Journal of Operational Research
Languages: English
Types: Article
Subjects: Modelling and Simulation, HB, Management Science and Operations Research, Information Systems and Management, HE

Classified by OpenAIRE into

arxiv: Computer Science::Networking and Internet Architecture
In this article we tackle the problem of co-ordinating transmission of data across a Wireless Mesh Network. The single task nature of mesh nodes imposes simultaneous activation of adjacent nodes during transmission. This makes the co-ordinated scheduling of local mesh node traffic with forwarded traffic across the access network to the Internet via the Gateway notoriously difficult. Moreover, with packet data the nature of the co-ordinated transmission schedule has a big impact upon both the data throughput and energy consumption. Perfect Periodic Scheduling, in which each demand is itself serviced periodically, provides a robust solution. In this paper we explore the properties of Perfect Periodic Schedules with modulo arithmetic using the Chinese Remainder Theorem. We provide a polynomial time, optimisation algorithm, when the access network routing tree has a chain or binary tree structure. Results demonstrate that energy savings and high throughput can be achieved simultaneously. The methodology is generalisable.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • Akyildiz, I. F., Wang, X., & Wang, W. (2005). Wireless mesh networks: a survey. Computer Networks, 47, 445-487.
    • Allen, S. M., Cooper, I. M., Glass, C. A., Kim, E.-S. Whitaker, R. M. (2012). Coordinating local schedules in wireless mesh networks. Working paper (
    • Bar-Noy, A., Bhatia, R., Naor, J., & Schieber, B. (2002a). Minimize service and operation costs of periodic scheduling. Mathematics of Operations Research, 27, 518-544.
    • Bar-Noy, A., Dreizin, V., & Patt-Shamir, B. (2004). Efficient algorithms for periodic scheduling. Computer Networks, 45, 155-173.
    • Bar-Noy, A., Nisgav, A., & Patt-Shamir, B. (2002b). Nearly optimal perfectly periodic schedules. Distributed Computing, 15, 207-220.
    • Bjorklund, P., Varbrand, P., & Yuan, D. (2004). A column generation method for spatial tdma scheduling in ad hoc networks. Ad Hoc Networks, 2(4), 405-418.
    • Brakerski, Z., Dreizin, V., & Patt-Shamir, B. (2003). Dispatching in perfectly-periodic schedules. Journal of Algorithm, 49, 219-239.
    • Brakerski, Z., Nisgav, A., & Patt-Shamir, B. (2006). General perfectly periodic scheduling. Algorithmica, 45, 183-208.
    • Brar, G., Blough, D., & Santi, P. (2006). Computationally efficient scheduling with the physical interference model for throughput improvemen tin wireless mesh networks. In Proceedings of ACM MobiCom 2006 (pp. 2-13).
    • Chen, W.-M., & Huang, M.-K. (2008). Adaptive general perfectly periodic scheduling. In Proceedings of the international symposium on ubiquitous multimedia computing (pp. 29-34).
    • Commander, C. W., & Pardalos, P. M. (2009). A combinatorial algorithm for the tdma message scheduling problem. Journal of Computational Optimization and Applications, 43(2), 449-463.
    • Das, A., Marks, R., Arabshahi, P., & Gray, A. (2005). Power controlled minimum frame length scheduling in TDMA wireless networks with sectored antennas. In Proceedings IEEE INFOCOM 2005 (pp. 1782-1793).
    • ElBatt, T., & Ephremides, A. (2004). Joint scheduling and power control for wireless ad-hoc networks. IEEE Transactions on Wireless Communications, 3, 74-85.
    • Ephremides, A., & Truong, T. (1990). Scheduling broadcasts in multihop radio networks. IEEE Transactions on Communications, 38(4), 456-460.
    • Goussevskaia, O., Oswald, Y. A., & Wattenhofer, R. (2007). Complexity in geometric sinr. In Proceedings of ACM MobiHoc 2007 (pp. 100-109).
    • Gupta, A., Lin, X., & Srikant, R. (2007). Low-complexity distributed scheduling algorithms for wireless networks. In Proceedings of IEEE INFOCOM 2007 (pp. 1631- 1639).
    • Hua, Q.-S., & Lau, F. C. (2008). Exact and approximate link scheduling algorithms under the physical interference model. In Proceedings of ACM DIALM-POMC workshop 2008 (pp. 45-54).
    • Jones, G. A., & Jones, J. M. (1998). Elementrary Number Theory. Springer.
    • Kim, E.-S., & Glass, C. A. (2014). Pefectly periodic scheduling for three basic cycles. Journal of Scheduling, 17(1), 47-65.
    • Li, Y., & Ephremides, A. (2007). A joint scheduling, powercontrol, and routing algorithm for adhoc wireless networks. Ad Hoc Networks, 5(7), 959-973.
    • Moscibroda, T., Wattenhofer, R., & Zollinger, A. (2006). Topology control meets sinr: the scheduling complexity of arbitrary topologies. In Proceedings of the 7th ACM international symposium on mobile adhoc networking and computing (pp. 310-321).
    • Papadaki, K., & Friderikos, V. (2008). Approximate dynamic programming for link scheduling in wireless mesh networks. Computers & Operations Research, 35(12), 3848-3859.
    • Patil, S., & Garg, V. K. (2006). Adaptive general perfectly periodic scheduling. Information Processing Letters, 98, 107-114.
    • Quintas, D., & Friderikos, V. (2012). Energy efficient spatial tdma scheduling in wireless networks. Computers & Operations Research, 39(9), 2091-2099.
    • Raman, B. (2006). Channel allocation in 802.11-based mesh networks. In Proceedings of 25th IEEE international conference on computer communications Infocom 2006. (pp. 1-10).
    • Sarkar, S., & Ray, S. (2008). Arbitrary throughput versus complexity tradeoffs in wireless networks using graph partitioning. IEEE Transactions on Automatic Control, 53(10), 2307-2323.
    • Sharma, G., Mazumdar, R. R., & Shroff, N. B. (2006). On the complexity of scheduling in wireless networks. In Proceedings of ACM MobiCom 2006 (pp. 227-238).
    • Wang, G., & Ansari, N. (1997). Optimal broadcast scheduling in packet radio networks using mean field annealing. IEEE Journal on Selected Areas in Communications, 15(2), 250-260.
    • Wolfram, R. (2008). Mathematica 7.0. Wolfram Research, Champaign, Illinois, US.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok