Security in residential and public areas is a matter of great importance for many people. This is why some Internet providers are offering surveillance systems as a value-added service. Such surveillance systems have recently shifted from CCTVs to IP-based cameras, as the latter offer clear advantages to their users, like a more competitive cost and being connected to the Internet. These systems are known as wireless surveillance sensor networks (WSSN).
For their video quality to be high enough, allowing to distinguish even patterns that may indicate intrusion or attack attempts, such a WSSN network must provide a high bandwidth. However, WSSNs make use of radio resources in unlicensed frequency bands, which are already highly populated by a wide range of devices with increasing demands of bandwidth. Hence, a more efficient management of the radio spectrum arises as a paramount problem.
Among the many solutions proposed for the problem of radio spectrum scarcity, some works focus on improving spectral efficiency 1, on error detection and correction algorithms 2, or on the design of new antennas for a more efficient signal reception 3. Some other works focus on the so-called frequency assignment problem (FAP) 4 and propose coordination mechanisms for devices sharing the same frequency band, with the aim of minimizing interferences and increasing throughput.
Such coordination mechanisms range from centralized approaches 5 to distributed heuristics like the commonly-used least congested channel search (LCCS) 6. In the recent work Automated Negotiation for Resource Assignment in Wireless Surveillance Sensor Networks 7, de la Hoz et al. explore a different approach, using automated negotiation techniques in order for the access points to negotiate the Wi-Fi channels, accounting for conflicting interests 8.
In order to apply these techniques to WSSNs, the authors have modeled such networks as a graph. The clusterhead is a device connected to (or integrated in) the Wi-Fi access point and, in addition to the cameras, there might be other wireless devices in the Wi-Fi network, which are connected to the Internet through their associated access point.
Hence, the graph has three types of vertices and two types of edges. Vertices can be access points (AP), cameras (C), or other wireless devices (D). Edges represent the following connections:
- Every wireless device (C or D) is connected to its closest AP, since it will use the channel assigned to its closest AP.
- A pair of nodes of type AP-AP is connected when the distance between them is below the interference radius R.
- Finally, since communications among the elements connected to the same AP are coordinated, pairs of type AP-C or AP-D are connected when the camera or device is not associated with that AP and pairs of type C-C or D-D when both cameras or devices are associated with different APs.
Frequency assignment problems have been often modeled as graph coloring problems, which are among the most prominent classes of problems in Discrete Mathematics 9. The most naive model uses graph nodes to represent elements to be assigned a frequency, edges to represent element pairs that should not be assigned the same frequency, and colors to represent frequencies. Thus, a proper coloring with hetero-chromatic edges guarantees a frequency assignment fulfilling the conditions.
However, Tragos et al. 10 concluded that this model is not accurate enough and suggested to incorporate into the graph the information regarding adjacent channel interferences. This is one of the key contributions in this paper, which models the interference power between two elements by weighting each edge according to three factors:
- A weight for each color pair (which can be understood as the interference between color and color ).
- A scaling of the previous weights according to the distance between edges’ endpoints.
- A factor accounting for the fact that a higher bandwidth data flow will occupy the wireless channel a higher fraction of the time.
In order to evaluate the goodness or utility of a particular coloring, i.e., a particular frequency assignment, the effect of both propagation and interferences over wireless signals has to be taken into account too. Hence, the utility at a particular node is closely related to the signal-to-interference plus noise ratio (SINR) 11. The utility of a coloring is just the sum of utilities of all the nodes in the network.
The experiments use different automated negotiation techniques to look for good colorings of the graph, which translate into frequency assignments (Wi-Fi channel assignments) with high utility. In particular, the authors have considered three types of WSSN scenarios:
- 50 APs and 350 () cameras.
- 50 APs and 500 () cameras.
- 100 APs and 500 () cameras.
The position of APs and wireless terminals in the plane is chosen at random, associating a wireless terminal to its closest AP. For each type of scenario and due to their randomness, the authors have generated three specific scenarios, for a total of nine scenarios. Moreover, given the non-deterministic nature of the different algorithms under study, each algorithm was run ten times in each scenario.
As mentioned above, in this paper Wi-Fi channels are assigned after a negotiation between the access points. The results show that negotiation techniques based in a Simulation Annealing (SA) voting algorithm outperform, in almost all cases, the standard technique SCS based in least congested channel search (LCCS). They are even able to outperform a nonlinear optimizer like ALHSO 12, after a non-difficult choice of configuration parameters (initial temperature) and (number of iterations).
The figure shows the mean value of the utility functions for the different scenarios, relative to their maximum value (in bold). Highlighted in green are those results that outperform or equal ALHSO. Highlighted in yellow are the results that outperform SCS. Results for a random color assignment and a Hill Climber (HC) voting algorithm are also included.
As the main conclusion, the use of negotiation techniques opens a door to a more efficient management of the radio spectrum. After all, reaching an agreement in apartment buildings might be easier for the Wi-Fi routers than for their owners…
- Au, E.; Cheong, M.; Ngo, C.; Cordeiro, C.; Zhuang, W. The future of Wi-Fi (Guest Editorial). IEEE Communications Magazine 2014, 52, 20–21. ↩
- Dalal, P.; Sarkar, M.; Dasgupta, K.; Kothar, N. Link Layer Correction Techniques and Impact on TCP’s Performance in IEEE 802.11 Wireless Network. Communications and Network 2014, 6, 49-60. ↩
- Liao, R.; Bellalta, B.; Oliver, M.; Niu, Z. MU-MIMO MAC Protocols for Wireless Local Area Networks: A Survey. IEEE Communications Surveys & Tutorials 2014, 18, 162-183. ↩
- Aardal, K.; van Hoesel, S.; Koster, A.; Mannino, C.; Sassano, A. Models and solution techniques for frequency assignment problems. Annals of Operations Research 2007, 153, 79-129. ↩
- Luna, F.; Alba, E.; Nebro, A.J.; Pedraza, S. Evolutionary algorithms for real-world instances of the automatic frequency planning problem in GSM networks. Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science 2007, 4446, 108-120. ↩
- Achanta, M. Method and Apparatus for Least Congested Channel Scan forWireless Access Points. U.S. Patent Application 10/959,446, 5 October 2006. ↩
- Enrique de la Hoz, Jose Manuel Gimenez-Guzman, Ivan Marsa-Maestre, and David Orden. Automated Negotiation for Resource Assignment in Wireless Surveillance Sensor Networks. Sensors 2015, 15, 29547-29568. DOI:10.3390/s151129547. ↩
- Ren, F.; Zhang, M.; Sim, K.M. Adaptive conceding strategies for automated trading agents in dynamic, open markets. Decision Support Systems 2009, 46, 704–716. ↩
- Tuza, Z. Graph coloring. In Handbook of Graph Theory; Gross, J.L., Yellen, J., Eds.; CRC Press: Boca Raton, FL, USA, 2004; Volume 25, pp. 408–438. ↩
- Tragos, E.Z.; Zeadally, S.; Fragkiadakis, A.G.; Siris, V.A. Spectrum Assignment in Cognitive Radio Networks: A Comprehensive Survey. IEEE Commun. Surv. Tutor. 2013, 15, 1108–1135. ↩
- Bazzi, A. On uncoordinated multi user multi RAT combining. In Proceedings of the IEEE Vehicular Technology Conference (VTC Fall), San Francisco, CA, USA, 5–8 September 2011; pp. 1–6. ↩
- Perez, R.E.; Jansen, P.W.; Martins, J.R.R.A. A Python-Based Object-Oriented Framework for Nonlinear Constrained Optimization. ↩