# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 1 Introduction  
In the last decade, multi-interface wireless networks have drawn the attention of practitioners and the research community. They are a widely used communication infrastructure which can support a plethora of different, important and popular applications such as file transfers. Multi-interface wireless networks are composed of heterogeneous devices that have different computational capabilities, are battery powered and can be equipped with different communication technologies such as Bluetooth, WiFi, 4G, 5G and GPRS. Mobile phones, laptops, smartwatches, tablets are but a few of the possible heterogeneous devices that can compose a multi-interface wireless network. They can activate one or more interfaces in accordance to the bandwidth of communication that is required, the cost (generally expressed as a percentage of the energy consumption) for maintaining an interface as active, the neighborhood. The activation of an interface has associated an energy cost. This must be carefully considered when establishing the desired connections since devices are battery powered. Suitable solutions should be devised to prolong the network lifetime. In this paper, we aim at finding the most energy efficient connections by activating a subsets of node interfaces. Actually, a fixed positive integer \(p\) is defined which indicates the maximum number of interfaces a single device can activate at most. We describe a multi-interface wireless network by using a graph \(G=(V,E)\), where \(V\) is the device set and \(E\) is the set of connections. This is defined by considering some parameters such as the distance between devices and the interfaces they share. Each \(v\in V\) is associated with an interface set \(W(v)\). The set \(\bigcup_{v\in V}W(v)\) defines all the available network interfaces; \(k\) denotes its cardinality. The endpoints of an edge that share at least one active interface can establish a connection. A node \(u\) consumes an energy \(c(\alpha)\) to keep the interface \(\alpha\) active. This provides a maximum communication bandwidth \(b(\alpha)\). Figure 1 shows a multi-interface wireless network where various devices such as mobile phones, smartphones, smartwatches, tablets and laptops can perform a point-to point communication by using different interfaces and protocols, i.e., IRdA, Bluetooth, Wi-Fi, GSM, 4G. It is worth noticing that each connection can be established by at least an interface; some devices are not directly connected although they share some interfaces. This can be consequence of different factors such as obstacles, distances and the protocols that are used for communication. A full instance specification could be provided (if necessary) by defining the cost of activating an interface on a specific device together with the interface bandwidth. This can be assumed equal among all devices while the energy spent to activate a specific interface may be different for different devices. We simplify the model by having a cost that refers to the percentage of battery consumed by each device. Effectively, the cost can be considered the same for each device with respect to a specific interface among the whole network. Nevertheless, different assumptions may lead to completely different problems that point out specific peculiarities of the multi-interface networks. In this paper, we study a variant of the _Coverage_ problem [1]. This is used to find the cheapest way to establish all connections that are defined by an input graph \(G\). The interfaces used for establishing a connection and bandwidths requirements are not considered. This problem only aims at ensuring that for each edge of \(G\) there is a common active interface at its endpoints. The objective is the minimization of the overall network activation cost. We add to the _Coverage_ problem a further constraint [2; 3; 4; 5] where a device cannot activate more than \(p\) interfaces. This constraint is used to keep under control the energy spent by single devices.