Capacitated Graph Theoretical Algorithms for Wireless Sensor Networks Towards Internet of Things

Introduction

In the present day when information is generated rapidly, distributed systems which are composed of autonomous devices connected via a communication link are the important part of information technology. Since data processing has been become simpler by grid computing, it took attention and became commercial thanks to cloud computing. In some conditions where traditional computer networks are not used due to environmental conditions, security issues, and power constraint; wireless sensor networks (WSNs) are used for habitat monitoring, border security, fire detection. WSNs have a crucial role in the Internet of Things (IoT) which aims to connect all devices to the internet, because of supplying heat, humidity, and light data to IoT via its sensor. A node can know only local information about the network in a distributed system. There is no point in collecting whole information about the distributed system to one node because of the message complexity and single point of failure. So, distributed algorithms modeled with local information are widely used.

WSNs can be modeled as undirected graph G (V, E) where V is set of the nodes and E is set of the bidirectional communication links. Each node v has a distinct identifier and aware of its neighbors that are indicated as N(v). δ(v) represents the number of neighbors of node v, in other words it is degree of node v. Δ is the maximum degree of given graph G (V, E). Graph-theoretical algorithms can be used for solving various network problems in WSNs. For example, backbone and infrastructure construction can be solved via spanning tree, domination set, independent set; clustering problem can be solved via graph partitioning; distributed storage problem and backup maintenance problem can be solved with graph matching; link monitoring can be modeled via vertex cover.

Capacitated graph-theoretical structures bring capacity constraint on known graph-theoretical problems and further complicate the problems. On the other hand, limiting the maximum node count of clusters, limiting the maximum link count of edges that are monitoring by monitor nodes, bringing a capacity constraint for distributed storage are some of the benefits of these structures. Capacitated vertex cover (CapVC) problem restricts the number of links covered by vertex. The distinction of the problem from vertex cover (VC) is that, while in vertex cover selected vertex v covers all incident edges, in CapVC each vertex v can cover a subset of at most c(v) edges incident to vertex v. In classical maximal graph matching problem (MM), the objective is to maximize the cardinality (or total weight) of matching set. Capacitated graph matching (so called b-matching) problem differs from the classical maximal matching problem by restricting the number of neighbors that a node can match with by a fixed capacity b(v). Considering dominating set problem (DS) for a given graph G(V, E), a dominating set D ⊂ V is a set such that every vertex v ∈ V \ D is dominated by u ∈ D. If it is required the produced set D to be connected, the problem is called connected dominating set (CDS). In capacitated version of these problems, the number of nodes dominated by node v is limited to c(v). Minimum spanning tree (MST) problem which aims at constructing the minimum weighted spanning tree, is widely used for routing in weighted topologies. Capacitated minimum spanning tree problem (CapMST) restricts the number of nodes contained in the sub-trees connected to a special node called the root node. CapMST is important in network design when terminal computers must be connected to a central node and star topology is not cost efficient.

Classical versions of aforementioned problems are in NP-Hard complexity class except for maximal matching and minimum spanning tree problems. Considering minimum dominating set, capacity constraint makes the problem harder than dominating set problem by restricting the number of nodes dominated by dominator nodes. Even though the capacitated matching problem seems to relax the MM problem by removing the one-to-one matching property, CapMM problem is in NP-Hard complexity (given a graph with weighted edges) class while MM can be solved in polynomial time.