Abstract
Current wireless networks mainly focus on delay-tolerant applications while demands for latency-sensitive applications are rising with VR/AR technologies and machine-to-machine IoT applications. In this paper we consider multi-channel, multi-radio scheduling at the MAC layer to optimize for the performance of prioritized, delay-sensitive demands. Our objective is to design an interference-free schedule that minimizes the maximum weighted refresh time among all edges, where the refresh time of an edge is the maximum number of time slots between two successive slots of that edge and the weights reflect given priorities. In the single-antenna unweighted case with k channels and n transceivers, the scheduling problem reduces to the classical edge coloring problem when \(k \ge \lfloor n/2 \rfloor \) and to strong edge coloring when \(k=1\), but it is neither edge coloring nor strong edge coloring for general k. Further, the priority requirement introduces extra challenges. In this paper we provide a randomized algorithm with an approximation factor of \(\tilde{O}\left( \max \left\{ \sqrt{\varDelta _p }, \frac{\varDelta _p}{\sqrt{k}} \right\} \log m \right) \) in expectation, where \(\varDelta _p\) denotes the maximum degree of the unweighted multi-graph, which is formed by duplicating each edge \(e_i\) for \(w_i\) times (\(w_i\) is \(e_i\)’s integral priority value), and m is the number of required link communications (\(f(n) \in \tilde{O}(h(n))\) means that \(f(n) \in O\left( h(n) \log ^k(h(n)) \right) \) for some positive constant k. The results are generalized to the multi-antenna settings. We evaluate the performance of our methods in different settings using simulations).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Schedules are restricted to be periodic because each non-periodic infinite schedule with a finite max weighted refresh time can be turned to a periodic schedule with the same refresh time. See Appendix for a proof.
- 2.
This is the case of \(\ell \)-hop interference model (wireless links \(\ell + 1\) or more hops away from one another can be scheduled to transmit data at the same time) when \(\ell =2\).
References
Al Islam, A.A., Islam, M.J., Nurain, N., Raghunathan, V.: Channel assignment techniques for multi-radio wireless mesh networks: a survey. IEEE Commun. Surv. Tutorials 18(2), 988–1017 (2015)
Balakrishnan, H., Barrett, C.L., Kumar, V.S., Marathe, M.V., Thite, S.: The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks. IEEE J. Sel. A. Commun. 22(6), 1069–1079 (2006)
Barrett, C.L., Istrate, G., Kumar, V.S.A., Marathe, M.V., Thite, S., Thulasidasan, S.: Strong edge coloring for channel assignment in wireless radio networks. In: Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOMW 2006), pp. 105–110, March 2006
Bicket, J., Aguayo, D., Biswas, S., Morris, R.: Architecture and evaluation of an unplanned 802.11 b mesh network. In: Proceedings of the 11th Annual International Conference on Mobile Computing and Networking, pp. 31–42. ACM (2005)
Chambers, B.: A rooftop ad hoc wireless network (2002). http://www.pdos.lcs.mit.edu/grid/
Chaporkar, P., Kar, K., Luo, X., Sarkar, S.: Throughput and fairness guarantees through maximal scheduling in wireless networks. IEEE Trans. Inf. Theory 54(2), 572–594 (2008)
Committee, L.S., et al.: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: High-Speed Physical Layer in the 5 GHZ Band, vol. 802, no. 1. IEEE Std., Piscataway (1999)
CREATE-NET and Technion: WING: wireless mesh network for next-generation internet (2012). http://www.wingproject.org. Accessed 15 June 2019
Ghosh, A., Wolter, D.R., Andrews, J.G., Chen, R.: Broadband wireless access with WiMax/802.16: current performance benchmarks and future potential. IEEE Commun. Mag. 43(2), 129–136 (2005)
Gonnet, G.H.: Expected length of the longest probe sequence in hash code searching. J. ACM (JACM) 28(2), 289–304 (1981)
Group, I.W., et al.: Part 11: wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Higher-Speed Physical Layer Extension in the 2.4 GHZ Band. ANSI/IEEE Std 802.11 (1999)
Hajek, B., Sasaki, G.: Link scheduling in polynomial time. IEEE Trans. Inf. Theory 34(5), 910–917 (1988)
Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718–720 (1981)
Joo, C., Lin, X., Shroff, N.B.: Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. In: IEEE INFOCOM 2008 - The 27th Conference on Computer Communications, pp. 1777–1785, April 2008
Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: End-to-end packet-scheduling in wireless ad-hoc networks. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, Philadelphia, PA, USA, pp. 1021–1030 (2004)
Mahdian, M.: The strong chromatic index of graphs. Dissertation, Department of Computer Science, University of Toronto (2000)
Nandagopal, T., Kim, T.E., Gao, X., Bharghavan, V.: Achieving MAC layer fairness in wireless packet networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pp. 87–98. ACM (2000)
Raab, M., Steger, A.: “Balls into Bins”—a simple and tight analysis. In: Luby, M., Rolim, J.D.P., Serna, M. (eds.) RANDOM 1998. LNCS, vol. 1518, pp. 159–170. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49543-6_13
Ramanathan, S., Lloyd, E.L.: Scheduling algorithms for multihop radio networks. IEEE/ACM Trans. Networking 1(2), 166–177 (1993)
Ramanathan, S.: A unified framework and algorithm for channel assignment in wireless networks. Wireless Netw. 5(2), 81–94 (1999)
Ramanathan, S., Lloyd, E.L.: Scheduling algorithms for multihop radio networks. IEEE/ACM Trans. Network. (TON) 1(2), 166–177 (1993)
Sharma, G., Mazumdar, R.R., Shroff, N.B.: On the complexity of scheduling in wireless networks. In: Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, MobiCom 2006, pp. 227–238. ACM, New York (2006)
Shi, H., Prasad, R.V., Onur, E., Niemegeers, I.G.M.M.: Fairness in wireless networks: issues, measures and challenges. IEEE Commun. Surv. Tutorials 16(1), 5–24 (2014)
Si, W., Selvakennedy, S., Zomaya, A.Y.: An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks. J. Parallel Distrib. Comput. 70(5), 505–524 (2010)
Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15(1), 14–19 (1982)
Wan, P.J., Frieder, O., Jia, X., Yao, F., Xu, X., Tang, S.: Wireless link scheduling under physical interference model. IEEE (2011)
Wan, P.J., Jia, X., Dai, G., Du, H., Wan, Z., Frieder, O.: Scalable algorithms for wireless link schedulings in multi-channel multi-radio wireless networks. In: INFOCOM, 2013 Proceedings IEEE, pp. 2121–2129 (2013)
Wu, X., Srikant, R., Perkins, J.R.: Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. IEEE Trans. Mob. Comput. 6(6), 595–605 (2007)
Acknowledgements
This work was supported in part by NSF grants CCF-1439084, CCF-1535900, CNS-1553510, CNS-1618391, CNS-1553273, and DMS-1737812.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
A Appendix: Omitted Proof
1.1 A.1 Proof on Schedule Periodicity
Given any infinite schedule S with a finite maximum refresh time, we can find a periodic schedule with max refresh time for each edge \(e_i\) no worse than that in S. Let the max refresh time of all edges in S be L. Consider the family of all possible schedules of the edges of G with no interference with length L. The number of these schedules is finite.
Now, let’s construct a periodic schedule \(S'\) from S. We divide S into sub-schedules of length L each. Since the configuration of these sub-schedules of length L is finite and S is infinitely long, there exists a subschedule M that repeats at some point in S. Extract the subschedule of S that starts from the first appearance of M and ends right before the second appearance of M. We now repeat this sub-schedule periodically and call it \(S'\).
Since each sub-schedule has length L, any edge \(e_i\) appears at least once in each sub-schedule. Thus, all the gap between two successive time slots of the same edge \(e_i\) in \(S'\) also happens in the original schedule S. Hence, the constructed periodic schedule has a maximum refresh time for each edge \(e_i\) which is no worse than that in the original schedule S. \(\square \)
B Evaluation
In this section, we evaluate our unweighted and weighted channel assignment algorithms under different scenarios in the single antenna case. Without loss of generality, we can assume that the smallest weight is 1 and all other weights are rounded to integer values. We consider model networks such as random node placement and perturbed grid placement with unit disk communication capacity, and also a real testbed network (denoted the Tmote network) which consists of 48 TMotes in a building that uses the ChipCon CC2420 radio. We vary network parameters such as node degree, the number of channels, weight distributions and measure the performance of our algorithms using the maximum fresh time divided by maximum (weighted) degree and \(\varDelta _p\) as the metric. For each network, we ran our algorithm 50 times to compute the average performance.
The network topology in Fig. 3 is constructed by throwing random nodes with a uniform circular range in a 2D unit square. This imitates random node placement in the wild. For each evaluation, we generate 50 networks. In Fig. 3.a, we increase the number of nodes in the unit square from 50 to 600 while keeping the average degrees the same (by scaling down the communication range of each node), so every node continues to have a similar number of interfering counterparts even when the network scale increases. The almost flat slopes of curves indicate that our algorithm still works as efficiently for large graphs as for small graphs when those graphs have similar densities. Besides, the result shows that when we have a reasonable number of channels, our algorithm can efficiently assign channels to a large network while keeping the latency low. In Fig. 3b, we increase the number of nodes but keep the communication range the same, i.e., when the number of nodes increases, the network becomes denser. That means a lot of implicit interferences occur. Therefore, the maximum refresh time increases unavoidably. Still, when we have a reasonable number of channels, our algorithm can keep the max refresh time moderate.
Random node placement often leads to many small holes in the network. To make the network more robust, perturbed grid placement is preferred which gives a more stable node degree among the network while reducing the number of gaps inside. Therefore, we often see an almost grid placement in real-world sensor networks. In order to evaluate on such wireless networks, we use a perturbed \(7\times 7\) grid placement network shown in Fig. 4a and also a Tmote network as shown in Fig. 4b. In the Tmote network, these nodes are deployed on walls and ceilings of a building. We collect traces of 3,600,000 packet transmissions using IEEE 802.15.4 standard for each pair of nodes. With the transmission traces, we define two nodes are connected if and only if the packet reception rate of its link is over \(90\%\).
In Fig. 5, we evaluate our algorithm on these two networks when weight distributions are uniform and power-law. In both networks, our algorithm can efficiently use channels to reduce the refresh time. However, when the weight distribution is power-law, the benefit diminishes because some implicit interference is unavoidable. Note that some edges have very high priorities and they contribute to the weighted degree which makes the maximum weighted degree pretty high. The ratio of the maximum weighted degree to the total weight is 0.32 for the perturbed grid and it is 0.12 for the Tmote network. The node with the maximum weighted degree creates more unavoidable interferences in the perturbed grid. Hence, the performance of the Tmote network is better than the one of the perturb grid. On the other hand, for both networks under the uniform distribution, the ratios are the same, 0.06, which is quite small and leaves room for improvement of our algorithm. When we vary the number of channels from one to two, our algorithm improves the most. It is almost twice as better than the case of only one channel.
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Tsai, SY., Yang, HT., Liu, K.S., Lin, S., Chowdhury, R., Gao, J. (2019). Multi-channel Assignment and Link Scheduling for Prioritized Latency-Sensitive Applications. In: Dressler, F., Scheideler, C. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2019. Lecture Notes in Computer Science(), vol 11931. Springer, Cham. https://doi.org/10.1007/978-3-030-34405-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-34405-4_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34404-7
Online ISBN: 978-3-030-34405-4
eBook Packages: Computer ScienceComputer Science (R0)