Budgeted constrained coverage on bounded carving-width and series-parallel multi-interface networks

The IoT vision often requires near-real-time data from physical and battery operated virtual devices in order to implement complex and critical services. In this paper, we consider the use of multi-interface wireless network communication for fast and energy efficient data transfer in a typical IoT scenario. Multi-interface wireless networks allow the interconnec- tion of battery-powered devices that can have different communication technologies such as Bluetooth, WiFi, 4G, 5G and GPRS. Devices can activate one or more interface depend- ing on the availability, required communication bandwidth, the cost (in terms of energy consumption) for maintaining an active interface, and the neighbourhood. Consider a network composed of heterogeneous devices. Each device might communi- cate by means of multiple interfaces. An intriguing research direction is that of activating (switch-on) a subset of interfaces for each device in such a way that suitable communica- tion connections are established. This means that the two devices at the endpoints of each connection must activate at least a same interface. This peculiarity inspired the modelling of what is called in the literature as Multi-Interface networks. Such a model has bee exten- sively investigated in the recent years. We consider a new variant where each interface is associated with both a cost and a profit, and also the establishment of a connection pro- vides a profit. Moreover, each device is limited to activate at most a fixed number q of its available interfaces whereas the overall cost of the interfaces that can be activated must be kept below a predefined budget b . Within this context we consider the Coverage prob- lem where the requirement is to establish all the connections defined by the edges of an undirected graph G = (V, E) , where nodes V represent the devices. We prove the problem is NP -hard even for the basic case of q = 2 . Then, we investigate the case of two well- established and related graph classes. Namely, we consider graphs with bounded Carving- width and Series-Parallel keeping parameter q = 2 . In both cases, we design two comple- mentary pseudo-polynomial time (in the size of the input) algorithms based on dynamic programming. Furthermore, for series-parallel graphs we also provide a fully polynomial time approximation scheme.