A crucial step during commissioning of wireless sensor and automation networks is assigning high-level node addresses (e.g., floor/room/fixture) to nodes mounted at their respective location. This address assignment typically requires visiting every single node prior to, during, or after mounting. For large-scale networks it also presents a considerable logistical effort. This paper describes a new approach to automatically assign high-level addresses without visiting every node. First, the wireless channel is simulated using a deterministic channel simulation in order to obtain node-to-node estimates of path loss. Next, the channel is measured by a precommissioning test procedure on the live network. In a third step, results from measurements and simulation are condensed into graphs and matched against each other. The resulting problem, identified as weighted graph matching, is solved heuristically. Viability of the approach and its performance is demonstrated by means of a publicly available test data set, which the algorithm is able to solve flawlessly. Further points of interest are the conditions that lead to high quality address assignments. 1. Introduction Building automation is not a new technology. However, with the advent of smart environments and the Internet of Things, the topic is again the focus of increased attention. This is especially true for wireless building automation systems, overlapping strongly with wireless sensor networks. This work deals with address assignment in wireless (building) automation networks, an underresearched topic, emerging primarily from experience with large-scale installations. By address assignment we mean attaching a high-level address which conveys locality (e.g., floor/room/fixture) to the nodes of the wireless network. The goal is, in other words, to produce a mapping from the addresses used by the MAC layer onto logical addresses based on location or role. Some protocols are explicit in their distinction between low-level address and high-level address. Other protocols, such as ZigBee, rely on low-level addresses for communication but support high-level roles with group membership or binding tables. High-level addresses become explicit again if dealt with in the context of a deployment plan or professional commissioning tool. Address assignment is a necessary step of commissioning of automation networks. While this work deals with both location and wireless channel measurements, it is different from the field of sensor node localization. Localization is typically a continuous problem; address assignment
References
[1]
T. King, T. Haenselmann, and W. Effelsberg, “On-demand fingerprint selection for 802.11-based positioning systems,” in Proceedings of the 9th IEEE International Symposium on Wireless, Mobile and Multimedia Networks (WoWMoM '08), Newport Beach, Calif, USA, June 2008.
[2]
S. Knauth, R. Kistler, D. K？slin, and A. Klapproth, “SARBAU - Towards highly self-configuring IP-fieldbus based building automation networks,” in Proceedings of the 22nd International Conference on Advanced Information Networking and Applications (AINA '08), pp. 713–717, Okinawa, Japan, March 2008.
[3]
B. D. Westphal, J. R. Hall, D. P. Bohlmann, and G. A. Zuercher, “BACnet protocol MS/TP automatic MAC addressing,” USPTO 12/326, 852, 2008.
[4]
G. Kiwimagi, C. McJilton, and M. Gookin, “Configuration application for building automation,” USPTO US, 2005/0119767 Al, 2004.
[5]
R. R. Lingemann, “Building automation system,” USPTO 10/608, 828, 2003.
[6]
L. Feri, G. M. P. J. Linnartz, J. W. Rietman, W. C. T. Schenk, C. J. Talstra, and H. Yang, “Efficient address assignment in coded lighting systems,” EPO EP, 2417834 Al, 2012.
[7]
A. Savvides, M. Srivastava, L. Girod, and D. Estrin, “Localization in sensor networks,” in Wireless Sensor Networks, Springer, New York, NY, USA.
[8]
J. Hightower and G. Borriello, “Location systems for ubiquitous computing,” Computer, vol. 34, no. 8, pp. 57–66, 2001.
[9]
R. Stoleru, J. A. Stankovic, and S. H. Son, “Robust node localization for wireless sensor networks,” in Proceedings of the 4th Workshop on Embedded Networked Sensors (EmNets '07), pp. 48–52, June 2007.
[10]
A. Papapostolou and H. Chaouchi, “WIFE: wireless indoor positioning based on fingerprint evaluation,” in Networking, vol. 5550 of Lecture Notes in Computer Science, 2009, Proceedings of the 8th International IFIP-TC 6 Networking Conference, Aachen, Germany, 2009.
[11]
P. Bahl and V. N. Padmanbhan, “RADAR: an in-building RF-based user location and tracking system,” in Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '00), pp. 775–784, Tel Aviv, Israel, 2000.
[12]
T. King, S. Kopf, T. Haenselmann, C. Lubberger, and W. Effelsberg, “COMPASS: a probabilistic indoor positioning system based on 802.11 and digital compasses,” in Proceedings of the 1st ACM International Workshop on Wireless Network Testbeds, Experimental Evaluation and Characterization (WiNTECH '06), pp. 34–40, usa, September 2006.
[13]
G. Zanca, F. Zorzi, A. Zanella, and M. Zorzi, “Experimental comparison of RSSI-based localization algorithms for indoor wireless sensor networks,” in Proceedings of the 3rd Workshop on Real-World Wireless Sensor Networks (REALWSN '08), pp. 1–5, April 2008.
[14]
N. Patwari, R. J. O'Dea, and Y. Wang, “Relative location in wireless networks,” in Proceedings of the 53rd Vehicular Technology Conference (VTS '01), pp. 1149–1153, May 2001.
[15]
C. Liu, T. Scott, K. Wu, and D. Hoffman, “Range-free sensor localisation with ring overlapping based on comparison of received signal strength indicator,” International Journal of Sensor Networks, vol. 2, no. 5-6, pp. 399–413, 2007.
[16]
C. Wan, A. Mita, and S. Xue, “Non-line-of-sight beacon identification for sensor localization,” International Journal of Distributed Sensor Networks, vol. 2012, Article ID 459590, 6 pages, 2012.
[17]
K. Sinha and A. D. Chowdhury, “A beacon selection algorithm for bounded error location estimation in ad hoc networks,” in Proceedings of the International Conference on Computing: Theory and Applications (ICCTA '07), pp. 87–92, Kolkata, India, March 2007.
[18]
R. A. Valenzuela, “Estimating Local Mean Signal Strength of Indoor Multipath Propagation,” IEEE Transactions on Vehicular Technology, vol. 46, no. 1, pp. 203–212, 1997.
[19]
G. J. M. Janssen, P. A. Stigter, and R. Prasad, “Wideband indoor channel measurements and BER analysis of frequency selective multipath channels at 2.4, 4.75, and 11.5？GHz,” IEEE Transactions on Communications, vol. 44, no. 9, pp. 1272–1288, 1996.
[20]
F. M. Landstorfer, “Wave Propagation Models for the Planning of Mobile Communication Networks,” in Proceedings of the 29th European Microwave Conference, pp. 1–6, Munich, Germany.
[21]
R. A. Valenzuela, S. Fortune, and J. Ling, “Indoor propagation prediction accuracy and speed versus number of reflections in image-based 3-D ray-tracing,” in Proceedings of the 48th IEEE Vehicular Technology Conference (VTC '98), pp. 539–543, May 1998.
[22]
Y. Rahmat-Samii, “GTD, UTD, UAT and STD: a historical revisit,” in Proceedings of the IEEE-APS Topical Conference on Antennas and Propagation in Wireless Communication, pp. 1145–1148, Cape Town, South Africa, 2012.
[23]
R. Sinkhorn and P. Knopp, “Concerning nonnegative matrices and doubly stochastic matrices,” Pacific Journal of Mathematics, vol. 21, no. 2, pp. 343–348, 1967.
[24]
D. Conte, P. Foggia, C. Sansone, and M. Vento, “Thirty years of graph matching in pattern recognition,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 18, no. 3, pp. 265–298, 2004.
[25]
H. A. Almohamad and S. O. Duffuaa, “Linear programming approach for the weighted graph matching problem,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, no. 5, pp. 522–525, 1993.
[26]
M. M. Zavlanos and G. J. Pappas, “A dynamical systems approach to weighted graph matching,” in Proceedings of the 45th IEEE Conference on Decision and Control (CDC '06), pp. 3492–3497, December 2006.
[27]
S. Umeyama, “Eigendecomposition approach to weighted graph matching problems,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, no. 5, pp. 695–703, 1988.
[28]
S. Gold and A. Rangarajan, “A graduated assignment algorithm for graph matching,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 4, pp. 377–388, 1996.
[29]
M. Zaslavskiy, F. Bach, and J.-P. Vert, “A path following algorithm for the graph matching problem,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 12, pp. 2227–2242, 2009.
