Basma Mostafa
email: basma.mostafa@lirmm.fr

Mohamed Saleh
email: m.saleh@fci-cu.edu.eg

Sally Kassem
email: s.kassem@fci-cu.edu.eg

Miklos Molnar
email: miklos.molnar@lirmm.fr

Abderrahim Benslimane Mostafa
email: abderrahim.benslimane@univ-avignon.fr

A Benslimane

An Energy-Efficient Multiobjective Scheduling Model for Monitoring in Internet of Things

To ensure robustness in wireless networks, monitoring the network state, performance and functioning of the nodes and links is crucial, especially for critical applications. This paper targets Internet of Things (IoT) networks. In the IoT, devices (things) are vulnerable due to security risks from the Internet. Moreover, they are resource-constrained and connected via lossy links. This paper addresses the optimized scheduling of the monitoring role between the embedded devices in IoT networks. The objective is to minimize energy consumption and communication overhead of monitoring, for each node. Several subsets of the potential monitoring nodes are generated by solving a minimal vertex cover (VC) problem with constraint generation. Assuming periodical functioning, VCs are optimally assigned to time periods in order to distribute the monitoring role throughout the entire network. The assignment of VCs to periods is modeled as a multiobjective generalized assignment problem. To further optimize the energy consumption of the monitors, they are sequenced across time periods to minimize the state transitions of nodes. This part of the problem is modeled as a traveling salesman path problem. The proposed model is tested on randomly generated instances and the experimental results illustrate its effectiveness to optimize the scheduled monitoring for fault tolerance in IoT networks. Index Terms-Energy-efficient monitoring, generalized assignment problem (GAP), Internet of Things (IoT), robustness, scheduling, traveling salesman path (TSP) problem, vertex cover (VC).

I. INTRODUCTION AND MOTIVATION

T HE Internet of Things (IoT) is a persistently grow- ing network that seamlessly interconnects a tremendous number of heterogeneous, smart devices (things) with the Internet. The connection does not require human-to-human

or human-to-computer interaction. The IoT adopts novel processing and communication architectures and technologies [START_REF] Vasseur | Interconnecting Smart Objects With IP: The Next Internet[END_REF]. IoT systems can rely on wireless sensor networks (WSNs) for data collection and their computational capabilities may be enhanced by employing cloud and fog/edge computing [START_REF] Shi | Edge computing: Vision and challenges[END_REF], [START_REF] Lin | A survey on Internet of Things: Architecture, enabling technologies, security and privacy, and applications[END_REF]. As a result, numerous applications and services have been created; including smart cities, smart homes, smart grids, smart energy, smart agriculture, and environmental and health care monitoring [START_REF] He | Coverage and connectivity in duty-cycled wireless sensor networks for event monitoring[END_REF].

The availability of devices, the reliability of communication, the quality of service (QoS), and security are all essential for the utilization of the IoT. Over time, the state of devices and the overall network may depreciate. This is due to the challenging and failure-prone nature of the IoT; consisting of a huge number of heterogeneous and resourceconstrained things in terms of memory, energy, and computational capability. Furthermore, energy constraints impose hard duty cycles to maximise longevity, which in turn causes unreliable connectivity [START_REF] Jara | The Internet of everything through IPv6: An analysis of challenges, solutions and opportunities[END_REF]. In addition to unknown and dynamic network topologies, and unreliable connectivity, this leads to incomplete information about the current network state [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF]. The situation is considered a form of entropy, where a system deteriorates unless effort is invested in the development of monitoring and correction mechanisms to maintain a faulttolerant system's performance [START_REF] Stankovic | Research directions for the Internet of Things[END_REF].

Fault tolerance can be tackled in the network deployment stage by guaranteeing full network coverage and connectivity [START_REF] Paradis | A survey of fault management in wireless sensor networks[END_REF]. In the network layer, multipath routing has a major role in fault tolerance. It utilizes the high density in node deployment to incorporate redundancy in routing paths; which in turn increases the chance of data delivery [START_REF] Ye | GRAdient broadcast: A robust data delivery protocol for large scale sensor networks[END_REF], [START_REF] Ganesan | Highly-resilient, energy-efficient multipath routing in wireless sensor networks[END_REF]. Nevertheless, constant network monitoring and taking corrective measures in case of failures is still necessary.

Consequently, the proliferation of IoT applications critically depends on effective monitoring methods and algorithms. To be effective, such methods and algorithms should do the following.

1) Ensure robustness and fault-tolerant operation of IoT ecosystems from end to end. 2) Guarantee good operation of sensors.

3) Verify the correctness of the big data programming models and the availability of resources in the network, in addition to. 4) Verify fog/edge and cloud datacenters, despite the high risk of faulty and nondeterministic environmental conditions.

Thus, addressing monitoring for fault tolerance and prevention in complex IoT can significantly improve the functioning of the network and will eventually pave way for the wide deployment of IoT services. This problem is interesting for both research and industrial domains, particularly for missioncritical, time-sensitive applications. Examples of such applications are critical control and fault detection, health monitoring and safety applications. Such applications require the availability, reliability, and the state of communicant objects to be constantly checked for fast restoration in cases of unexpected communication problems.

The literature is rich with researches on monitoring WSNs [START_REF] Paradis | A survey of fault management in wireless sensor networks[END_REF], [START_REF] Swain | Heterogeneous fault diagnosis for wireless sensor networks[END_REF]- [START_REF] Zhao | Residual energy scan for monitoring sensor networks[END_REF], but fewer researches tackled the problem of monitoring IoT networks. Obviously the large foundation built for WSNs paves the way for successful monitoring in the IoT. However, due to the intrinsic differences between the two paradigms, providing a monitoring system customized specifically for IoT networks and their standardized protocols is worth investigating. Therefore, this paper is motivated by the lack of research that has addressed monitoring IoT efficiently, in terms of energy consumption and communication overhead.

The monitoring system operations allow continuous maintenance of the network state and the availability of components. The system needs to consider the resulting overhead on the network and minimize it. The ability to monitor a network in real-time with energy-efficient and dynamic algorithms helps in the early detection/prevention of faults. At the same time, the network is left unconstrained during normal operation. This objective is challenging, since network monitoring causes high energy losses due to the need for devices to be awake most of the time to maintain a correct network state [START_REF] Devi | Survey on sleep scheduling methods in wireless sensor networks[END_REF]. On the other hand, the design of WSNs, and low power and lossy networks (LLNs), is ordinarily constrained by life span concerns. A prevalent approach toward expanding the life span of such networks is by using sleep scheduling. In sleep scheduling, nodes enter sleep state frequently, and intermittently wake up to check for action in the network [START_REF] Keshavarzian | Wakeup scheduling in wireless sensor networks[END_REF], [START_REF] Molnár | Quasi-optimal scheduling algorithm for area coverage in multi-functional sensor networks[END_REF]. For critical and time-sensitive IoT applications, monitoring needs to be continuous regardless of the lack of activity in the network. Therefore, while employing monitoring with sleep scheduling, it is required to guarantee that each link in the network is always monitored by at least one monitoring node throughout the network lifetime. Ignoring the monitoring overhead may lead to increased congestion in the network at critical times, or battery drainage. These situations violate the requirements of mission-critical, time-sensitive IoT applications.

This paper investigates the optimized scheduling of the monitoring role of nodes in IoT networks. The problem is represented through a mathematical model. The developed model corresponds to a multiobjective optimization of the energy consumption and the overall communication overhead of monitoring the network. The proposed model is decomposed into a three-phase framework. The first phase requires generating multiple subsets of the nodes that cover the entire graph. These subsets are generated by solving a vertex cover problem (VCP) iteratively; while incorporating a constraint generation algorithm. Furthermore, an optimized scheduling of the vertex covers (VCs) is proposed. The scheduling aims to minimize the energy and communication costs incurred while monitoring the network. QoS-aware monitoring is targeted, where constraints are used to include/eliminate the nodes that can/cannot withstand the energy requirements of monitoring. The scheduling is addressed in the second and third phases of the computation, which are modeled as a multiobjective generalized assignment problem (GAP) and a traveling salesman path (TSP) problem, respectively. To verify the effectiveness of the proposed model, a branch-and-bound (BB) algorithm is used for the first and second phases and a dynamic programming algorithm is used for the third phase. This contribution is a step toward achieving optimized monitoring for improved robustness and fault tolerance. The monitoring process is performed with minimal energy consumption and communication overhead while providing load balancing. This is important for mission-critical IoT applications.

The rest of this paper is organized as follows. Section II discusses literature related to network monitoring in the IoT and WSNs. Section III is a description of the problem statement. Section IV presents the modeling of the monitoring optimization. Section V presents the mathematical formulation of the proposed framework, followed by implementation and analysis in Sections VI and VII, respectively. The conclusions and future research are presented in Section VIII.

II. RELATED WORK

Several applications of the IoT are known for area, object, and health monitoring [START_REF] Razafimandimby | Efficient Bayesian communication approach for smart agriculture applications[END_REF]- [START_REF] Jara | Interconnection framework for mHealth and remote monitoring based on the Internet of Things[END_REF]. This research targets monitoring the IoT network itself (hereinafter referred to as network monitoring). Algorithms are developed for ensuring a reliable and fault-tolerant operation of the network. Fault tolerance can be addressed in each of the network (routing) layer, transport layer or application layer [START_REF] Paradis | A survey of fault management in wireless sensor networks[END_REF]. Focusing on the network layer, the objective is to provide stable, reliable, and scalable end-to-end connectivity.

Extensive work had been proposed in the literature to address the problem of network monitoring for fault tolerance in WSNs [START_REF] Swain | Heterogeneous fault diagnosis for wireless sensor networks[END_REF]- [START_REF] Zhao | Residual energy scan for monitoring sensor networks[END_REF], [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF]. Swain et al. [START_REF] Swain | Heterogeneous fault diagnosis for wireless sensor networks[END_REF] proposed a clustering framework for fault diagnosis to balance the load and minimize the energy consumption. The authors used a statistical mechanism for fault detection and neural networks for fault classification. Panda and Khilar [START_REF] Panda | Distributed self fault diagnosis algorithm for large scale wireless sensor networks using modified three sigma edit test[END_REF] proposed a statistical-based, distributed fault diagnosis algorithm. Coordination between neighboring nodes was used in the fault diagnosis to minimize the communication overhead. Khan et al. [START_REF] Khan | Application of fuzzy inference systems to detection of faults in wireless sensor networks[END_REF], on the other hand, proposed a fault detection strategy for WSNs based on a fuzzy inference system.

Most of the proposed techniques are considered to be either active or passive monitoring [START_REF] Paradis | A survey of fault management in wireless sensor networks[END_REF], [START_REF] Andreozzi | On the integration of passive and active network monitoring in grid systems[END_REF]. Active monitoring injects probes into the network to infer the network's performance from the measured parameters (such as delays and packet losses). Alternatively, passive monitoring observes the traffic that normally passes through the network and infers the network's performance from it. Examples of active and passive monitoring for WSNs are found in [START_REF] Zhao | Residual energy scan for monitoring sensor networks[END_REF] and [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF], respectively.

Given that the design of WSN, and LLNs is always constrained by life span concerns, prolonging the lifetime of the nodes has become a problem of paramount importance. The problem is called in the literature the maximum lifetime problem (MLP). Cardei et al. [START_REF] Cardei | Energy-efficient target coverage in wireless sensor networks[END_REF] proved that MLP is NPcomplete. Since monitoring uses the energy of the nodes, this additional activity should be minimized to prolong the network lifetime as much as possible.

Lifetime maximization can be reached by using the high redundancy feature in node deployment, specifically, by collecting the nodes into subsets known as covers. Each target must be monitored by at least one sensor in the cover. Extending the network lifetime can be achieved by scheduling between these covers, where the monitoring role is alternated between different subsets. The sensors that are not currently monitoring switch to a sleep state, where the energy consumption is minimal. The total energy consumption of a node must be at most equal to its initial energy. Several propositions were formulated in the literature to address MLP and problem variations [START_REF] He | Coverage and connectivity in duty-cycled wireless sensor networks for event monitoring[END_REF], [START_REF] Molnár | Quasi-optimal scheduling algorithm for area coverage in multi-functional sensor networks[END_REF], [START_REF] El-Moukaddem | Maximizing network topology lifetime using mobile node rotation[END_REF], [START_REF] Cho | An energy scheduling algorithm for ensuring the pre-determined lifetime in sensor network[END_REF].

Although the literature is rich with many researches on monitoring in WSNs [START_REF] Paradis | A survey of fault management in wireless sensor networks[END_REF], [START_REF] Swain | Heterogeneous fault diagnosis for wireless sensor networks[END_REF]- [START_REF] Zhao | Residual energy scan for monitoring sensor networks[END_REF], [START_REF] Liu | Robust monitor assignment with minimum cost for sensor network tomography[END_REF], most of the researches proposed for WSNs are based on the assumptions that the network does not have a central controlling node, and that nodes are not associated with a unique global address [START_REF] Raza | SVELTE: Real-time intrusion detection in the Internet of Things[END_REF]. On the other hand, IoT networks always include a central control device, known as the border router (BR), which connects IPv6 over LoWPANs (6LoWPAN) networks with the Internet. The BR is assumed to be always accessible [START_REF] Kushalnagar | IPv6 Over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals[END_REF], [START_REF] Sheng | A survey on The IETF protocol suite for the Internet of Things: Standards, challenges, and opportunities[END_REF], therefore it is capable of performing a crucial role in monitoring. Moreover, nodes are globally identified by an IP address which facilitates active monitoring when checking the availability of networks' components, where communication has not been established for long times. The full integration with the Internet infrastructure and cloud services further enhances the computation capabilities of IoT networks, which could also be beneficial for monitoring.

Despite these favorable characteristics, ensuring a reliable, fault-tolerant communication for IoT networks remains a challenging task for the following reasons.

1) The IoT is enabled by resource-constrained and heterogeneous things that are connected to the insecure Internet.

2) The utilized protocols need to be optimized to minimize the overhead on the constrained things. 3) Things are globally accessible which imposes a huge security risk from the Internet. 4) The communication is unreliable as they are connected through lossy links [START_REF] Raza | SVELTE: Real-time intrusion detection in the Internet of Things[END_REF]. 5) Furthermore, there are challenges imposed due to node mobility and the dynamic and uncertain environmental conditions. To enable the IoT, the Internet Engineering Task Force (IETF) working group has defined IPv6 over LoWPANs [START_REF] Kushalnagar | IPv6 Over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals[END_REF]. It was promised to provide end-to-end connectivity, ubiquity, and scalability. However, due to the resource-constrained nature of the nodes, crucial IP protocols that are usually incorporated for network monitoring cannot be supported by such nodes. Therefore, extra effort has to be spent to address optimized network monitoring for IoT networks. Several recent works were proposed to answer to the security requirements of the IoT [START_REF] Raza | SVELTE: Real-time intrusion detection in the Internet of Things[END_REF]- [START_REF] Sedjelmaci | An accurate security game for low-resource IoT devices[END_REF]. For instance, Raza et al. [START_REF] Raza | SVELTE: Real-time intrusion detection in the Internet of Things[END_REF] developed an intrusion detection system to catch routing attacks in the IoT. Giuliano et al. [START_REF] Giuliano | Security access protocols in IoT capillary networks[END_REF] proposed a key renewal algorithm for the secure access of devices.

Additionally, The IETF working group standardized the routing protocol for LLNs (RPL). It is considered to be the de facto routing protocol for IP-connected IoT [START_REF] Kushalnagar | IPv6 Over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals[END_REF], [START_REF] Sheng | A survey on The IETF protocol suite for the Internet of Things: Standards, challenges, and opportunities[END_REF]. It was developed as a response to the routing requirements of LLNs [START_REF] Martocci | Building Automation Routing Requirements in Low Power and Lossy Networks[END_REF]. Multipath routing as well as local and global routing structure repair mechanisms were proposed to handle unreliable connectivity in IP-connected IoT. Multipath routing utilizes the high density in node deployment to incorporate redundancy in routing paths. It contributes to fault tolerance as it facilitates the recovery of the routing structure in case of link failures which increases the chance of data delivery and provides load balancing [START_REF] Paradis | A survey of fault management in wireless sensor networks[END_REF]- [START_REF] Ganesan | Highly-resilient, energy-efficient multipath routing in wireless sensor networks[END_REF].

RPL repair mechanisms are considered to be reactive to node or link failures. Consequently, delays in communications and nodes unreachability are expected for some time (possibly for several minutes) [START_REF] Korte | A study of the RPL repair process using ContikiRPL[END_REF]. Such delays are unacceptable for critical, time-sensitive IoT applications. Thus, network monitoring is a requirement. It is imperative, and yet challenging, to develop monitoring systems compatible with these standards and adapted to the mentioned challenges and characteristics. This led to development of a monitor placement algorithm that works in tandem with RPL in [START_REF] Mostafa | Distributed monitoring in 6LoWPAN based Internet of Things[END_REF]. The algorithm is modeled as a classical minimum VCP that works in tandem with IPv6 routing protocol for LLNs (RPL) The VCP works on the destination oriented directed acyclic graphs (DODAG) constructed by RPL. A polynomial-time algorithm that converts the DODAG into a nice-tree decomposition with unity treewidth was developed in [START_REF] Mostafa | Distributed monitoring in 6LoWPAN based Internet of Things[END_REF]. This strategy yielded a significant reduction in the complexity of solving the originally NP-hard VCP on generic graphs to be only polynomial-time solvable on DODAGs. In this paper, an energy-efficient monitoring algorithm is proposed to maintain reliable network structure, while minimizing the overhead monitoring imposes on the network.

III. PROBLEM STATEMENT

The problem addressed is the efficient, full monitor coverage in RPL-based 6LoWPAN networks for a predetermined lifetime, considering minimum energy consumption and communication overhead. In RPL, the BR is responsible for the DODAG construction, which starts by broadcasting a DODAG information object (DIO) [START_REF] Sheng | A survey on The IETF protocol suite for the Internet of Things: Standards, challenges, and opportunities[END_REF]. The DIO contains the configuration of the DODAG. The objective of this paper is to continuously test the availability and correct functioning of neighboring nodes by monitoring the status of the entire set of links present in the network.

Monitoring can be performed inside RPL by including a header in the DIO for metrics and constraints objects. This header is called DAG metric container object. Node energy and link reliability are examples of the metrics/constraints that could be included in the DAG metric container object [START_REF] Vasseur | Routing Metrics Used for Path Calculation in Low Power and Lossy Networks[END_REF]. When the DIO traverses the DAG, each node augments a subobject to the message, which expresses its value to the metric used. The monitored nodes will unicast their responses of the DIOs to their monitors. Monitors are the nodes responsible for gathering the monitoring data and reporting back to the BR, through multihop communication. The BR then sends this information to the networks operations center (NOC), where data analysis is performed.

It is assumed that a link can only be monitored by its extremities (i.e., endpoints). Also, each node has several activities independent from monitoring; therefore, the monitoring activity cannot consume more than a specified limited power (fraction of a node's battery). The intrinsic energy limitations of the resource-constrained things in IoT networks need to be taken into consideration. This is because a monitor cannot continuously monitor its neighbors without running out of the battery reserved for monitoring.

As mentioned in Section I, sleep scheduling is usually incorporated in WSNs and LLNs to reduce average power consumption and maximize longevity. This is often achieved by duty cycling between active and sleep states of the nodes. Hence, in order to achieve continuous monitoring, it is imperative to alternate the monitoring duty between several sets of nodes, while ensuring that each set is capable of covering the entire network. It should be noted that the active/sleep alternation addressed in this context is the turn on/off of the monitoring activity of the node, regardless of the other activities a node may perform (sensing, transmitting of sensed data, etc.). To realize this alternation, the monitoring function is periodical across the planning horizon. The planning horizon is the predetermined lifetime specified by the NOC in which all edges are being monitored. The NOC is responsible for planning the optimized periodic monitor scheduling. Therefore, the optimization is external from the resourceconstrained things. At any time interval, the active node set is known from the DODAG.

Usually, the cost of monitoring a network includes a monitor deployment cost and an operational cost [START_REF] Salhi | Anomaly detection joint optimization of monitor location and network anomaly detection[END_REF]. The deployment cost is the hardware cost of deploying monitoring nodes. For the problem in hand, the operational cost is the network overhead resulting from the communications between the monitoring devices and the BR. The monitors are ultimately transmitting the gathered information about the monitored nodes to the root of the DODAG. The transmission is done through multihop communication. Consequently, the longer the path to the root in number of hops, the higher is the cost. Moreover, the monitoring activity consumes a percentage from the battery reserved for monitoring. This paper aims to minimize the monitoring costs in terms of communication and energy costs.

As mentioned above, in sleep scheduling, a node assumes different states: active state, sleep state, or transient state (from active to sleep and vice versa). The energy consumption during the transient state can be high [START_REF] Ma | Energy efficient TDMA sleep scheduling in wireless sensor networks[END_REF], and numerous state transitions for the nodes consume extra energy [Fig. 1(a)]. Consequently, the energy consumption of the monitors could further be minimized if the time periods, where a node is To that end, it is required to find the optimal sequencing between the sets of monitors across the time periods in a way that minimizes the state transitions of nodes. The modeling and mathematical formulation of the monitoring optimization are discussed in the following section.

IV. MODELING OF MONITORING OPTIMIZATION

The IoT network could be represented by its logical graph constructed by the routing protocol RPL, namely the DODAG [START_REF] Razafimandimby | Efficient Bayesian communication approach for smart agriculture applications[END_REF], [START_REF] Fang | An integrated system for regional environmental monitoring and management based on Internet of Things[END_REF]. Consider an active DODAG D = (V, E), where V represents all the vertices, V = {v k , k = 1, 2, . . . , q} and E is the set of edges. For monitoring a time horizon T = {T j , j = 1, . . . , n}, the duty is cycled between several sets of nodes; each node has a reserved battery for monitoring (Reserved_battery k ). The monitoring activity for one period consumes energy (E m ). During the lifetime of monitoring, communication and transition costs are incurred. The communication cost is the cost of transferring the monitoring data to the BR. Transition cost is the cost of alternating from one set of monitors to another. The objective is to minimize the overall monitoring costs while ensuring monitor coverage of the entire DODAG throughout the planning horizon.

Scheduling between several sets of monitors for minimum energy consumption is an NP-hard problem. This remains true even in the very special case, where, the Reserved_battery k for monitoring is sufficiently large such that, one set of monitors can cover the entire planning horizon. Finding the minimum set of vertices to cover an entire graph is also NP-hard [START_REF] Bourgeois | Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms[END_REF], [START_REF] Åstrand | Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks[END_REF]. To the best of our knowledge, the exact solution to the defined problem is not known. In this paper, a three-phase decomposition of the problem (Fig. 2) is proposed. The three proposed phases are modeled using well-known optimization problems in the literature. Although these problems are NP-hard in nature, approximation algorithms to solve them are available in the literature (see [START_REF] Bourgeois | Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms[END_REF]- [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF]). Moreover, decomposing the original problem allows a finer reduction of the search space and, hence, reduction in the solution's complexity.

The first phase (Phase I) of the proposed decomposition is responsible for creating multiple sets of monitoring nodes. Each set satisfies the coverage requirements of the network. Phase I can be modeled as a VCP [START_REF] Balaji | Optimization of unweighted minimum vertex cover[END_REF]. The objective is to find the minimal sets of vertices that cover all the edges in the graph. The graph used in this paper, is the DODAG constructed by RPL [START_REF] Kushalnagar | IPv6 Over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals[END_REF], [START_REF] Sheng | A survey on The IETF protocol suite for the Internet of Things: Standards, challenges, and opportunities[END_REF]. Only minimal VC sets are interesting for monitoring. If a node set is not minimal for the VCP then it contains a subset which is minimal and can cover all the edges with less cost.

As described in Section III, several monitoring sets (VCs) are required to achieve monitor scheduling while minimizing and balancing the energy consumption of the monitors. For this purpose, an algorithm (Algorithm 1) is developed to get multiple of VCP, after incrementally adding new constraints to reduce the search space. Reducing the search space through incrementally adding new constraints is known as the constraint generation approach [START_REF] Boots | A constraint generation approach to learning stable linear dynamical systems[END_REF].

The output of Phase I is several sets of VCs. The working schedule of the VCs across the planning horizon is still required. Given a planning horizon (defined by the NOC), divided into several time periods, the purpose of Phase II is to optimally assign (a subset of) the VCs to each of the time periods with the following objectives.

1) The total energy consumed for monitoring is minimized.

2) The communication cost across all VCs is minimized.

Phase II is modeled as a GAP [START_REF] Pentico | Assignment problems: A golden anniversary survey[END_REF]. GAP is a special type of optimization problems, where agents are assigned to perform multiple tasks (Fig. 3). For the problem in hand, agents are the VC sets (or a subset of them) that should be assigned to time periods.

The last phase, Phase III, is sequencing the VCs with the objective of minimizing nodes' state transitions from one period to the next. The sequence generated determines

Model 1: Minimum VCP Decision Variables Let v k = 1, if v k is chosen in a Vertex Cover 0, if v k is not chosen in a Vertex Cover (2) Model Equations Minimize q k=1 v k ( 3
)
Subject to v i + v j ≥ 1 ∀ v i , v j ∈ E (4) v k ∈ {0, 1} ∀ v k ∈ V (5)
the number of times a node's state is being changed from asleep to awake and vice versa. Phase III is modeled as a TSP problem [START_REF] Lam | Traveling salesman path problems[END_REF]. We are interested in finding the minimum weighted Hamiltonian path (HP) (in terms of nodes state transitions) from an arbitrary starting point. A HP is a path that visits each vertex exactly once without the need to return to the starting vertex [START_REF] Roy | Stochastic Dynamics, Filtering and Optimization[END_REF]. The vertices in this case are the selected VCs from Phase II. The starting vertex of the HP is completely arbitrary. The edges represent the transition costs.

The result (the path) gives the optimal sequence (scheduling) of the selected VCs.

V. MATHEMATICAL FORMULATION OF MONITORING OPTIMIZATION

The three phases include the following sets. 1) Set V: Represents all the vertices in the DODAG, where V = {v k , k = 1, 2, . . . , q}.

2) Set S: Represents all the VCs VC obtain-ed from

Phase I, where subset VC ⊂ V represents the subset of monitoring nodes and S = {vc i , i = 1, 2, . . . , m}. 3) Set T: Contains the disjoint time periods covering the entire planning horizon; which the VCs are assigned to monitor. T = {T j , j = 1, . . . , n}.

A. Phase I: Generating Multiple Vertex Covers

Let D = (V, E) be the DODAG, where V is the set of vertices and E is the set of edges. A subset VC ⊂ V is a minimal VC of D if for every edge (u, v) ∈ E, either u ∈ VC or v ∈ VC or both u, v ∈ VC and VC is irreducible, i.e., no vertex can be removed from the VC without losing the coverage property.

Phase I computes set S which includes the m VCs such that for each edge in the DODAG at least one of its endpoints belongs to vc i . Moreover, no VC in S should be a subset of another such that ∀ vc i ⊂ S, vc j ⊂ S|vc i ⊂ vc j .

(

) 1
Let the decision variables v k express whether the vertex v k is in the VC or not. The objective is to minimize the total number of vertices in the VC, subject to the constraint that at least one vertex of the edge (v i , v j ) is a member of the VC.

The problem is the binary optimization problem represented by Model 1.

Algorithm 1: VCP With Constraint Generation

Input: DODAG D, Initial solution vc i , initial matrix of constraints A, vector of RHS b, and the initial value of the objective function z.

Output:

Matrix of solutions M Step 1 While (feasible minimal VC do exist) do

Step 1.1

M← vc i Step 1.2 A← A +vc T i Step 1.3 b← b + (z i -1) Step 1.4 i←i +1 Step 1.5 (vc i , z) = VCP (A, b ) END While Step 2 Return M END
The binary integer program in Model 1 is solved to get the minimum set of monitors, i.e., the minimum VC. In order to obtain multiple VCs, Algorithm 1 is used to solve the VCP iteratively. Each VC obtained using Algorithm 1 satisfies the constraints of Model 1.

Algorithm 1 works as follows: construct a matrix M, where all solutions of the VCP are stored, and a z vector which contains the corresponding objective function value to each solution in M. Initially, M contains the optimum solution obtained after solving Model 1 using BB algorithm, and z stores the minimum VC.

Then, the VCP is solved iteratively after adjusting the integer program by adding previous solutions to the set of constraints, thereby reducing the search space. The algorithm terminates when no other feasible minimal VCs can be found. In each iteration, a column representing the new solution, which has a cardinality greater than or equal to the previous solution, is appended to matrix M and the corresponding objective function value is added to the z vector, such that

vc T i * M < z. ( 6
)
To illustrate, let the initial solution be vc 1 , and the corresponding objective function value be z 1 . To obtain vc 2 , solve the integer program Ax ≤ b after adding the following constraint to the matrix of constraints (A) and the vector of RHS (b):

vc T 2 * vc 1 < z 1 . ( 7
)
In this way, to solve for vc 3 the following two constraints are appended:

vc T 3 * vc 1 < z 1 (8) vc T 3 * vc 2 < z 2 . ( 9
)
To solve for vc m the following (m -1) constraints are appended:

vc T m * vc 1 < z 1 (10) . . . vc T m * vc m-1 < z m-1. ( 11
)

B. Phase II: Assigning Time Periods to Vertex Covers

In Phase II, the planning horizon is divided into several periods. Then, a mathematical model is developed to optimally associate the VCs to periods throughout the planning horizon. The assignment does not define any ordering or sequencing of the time periods. Given a planning horizon denoted by T = {T j , j = 1, . . . , n}, define a binary decision variable s ij that indicates whether a VC vc i is assigned to monitor a period T j [refer to [START_REF] Zhao | Residual energy scan for monitoring sensor networks[END_REF]].

Assumptions: 1) Any node can be selected as monitor.

2) A node may be a member of several VCs.

3) Some VCs may monitor one period, more than one period, or none at all. 4) Each period is to be assigned exactly one VC. 5) The monitoring cost is defined in terms of the communication cost incurred by monitors and the energy loss due to monitoring. Any node v k may be a member of several VCs. The current Consumed_energy k of node v k is calculated using [START_REF] Devi | Survey on sleep scheduling methods in wireless sensor networks[END_REF]. Equation [START_REF] Devi | Survey on sleep scheduling methods in wireless sensor networks[END_REF] states that: the current Consumed_energy k for monitoring, depends on the number of times a VC set, including v k , has been assigned to a period, multiplied by the energy loss (E m ) per each monitoring period. The energy loss is the same for each active monitor and for each period. In [START_REF] Panda | Distributed self fault diagnosis algorithm for large scale wireless sensor networks using modified three sigma edit test[END_REF], a binary variable y ki is defined, which indicates whether a vertex v k is a member of VC vc i or not. The variable y ki is the output of Phase I, and hence it is a parameter in Phase II. When y ki is multiplied by s ij and summed over the VCs and the periods, the result is the number of times a vertex v k has been assigned to monitor a period [refer to [START_REF] Devi | Survey on sleep scheduling methods in wireless sensor networks[END_REF]].

Energy is lost due to communication between the monitoring devices and the BR. This is because the monitors are ultimately transmitting the gathered information about the monitored nodes to the root of the DODAG. The energy lost for communicating the monitoring data is not part of the Reserved_battery k for monitoring. On the other hand, this energy loss affects the rest of the battery that is not dedicated to monitoring. Accordingly, it is necessary to find the shortest path, in terms of the number of hops to the BR. The objectives in Phase II are twofold [refer to ( 16)-( 18)]. At this stage, it is required to determine how all assignments should be made while minimizing the total number of hop counts traveled by all members of the VCs. This is done while minimizing the total energy spent for all nodes. Equation ( 12) denotes the number of hops traveled from each monitoring node v k in vc i to the root as h k , and (13) denotes the total number of hops traveled by all v k in vc i as H i . Constraint [START_REF] Fang | An integrated system for regional environmental monitoring and management based on Internet of Things[END_REF] indicates that each period must be monitored by one VC. Constraint [START_REF] Jara | Interconnection framework for mHealth and remote monitoring based on the Internet of Things[END_REF] ensures that the energy consumed for monitoring never exceeds the (Reserved_battery k ).

C. Phase III: Sequencing Between Assigned Vertex Covers

The objective of Phase III is to minimize the nodes' state transitions from one VC to the next. If a node v k belongs to more than one VC set vc i , the model associates consecutive periods to the VC sets containing the repeated node.

Model 2: Genaralized Assignment Problem Parameters:

y ki = 1, if v k ∈ vc i 0, otherwise (12
Let s ij = 1, if vc i is assigned to period j 0, otherwise (14)
Auxiliary Variables:

Consumed_energy k = E m * ⎛ ⎝ m i=1 n j=1 y ki * s ij ⎞ ⎠ ( 15
)
Objective Functions: (H i ) * s ij [START_REF] Molnár | Quasi-optimal scheduling algorithm for area coverage in multi-functional sensor networks[END_REF] Model Equations:

Minimize F 1 & F 2 ( 18
)
Subject to:

m i=1 s ij = 1, ∀ j ∈ T (19)
Consumed_energy k ≤ Reserved_battery k ∀ k ∈ V (20) s ij ∈ {0, 1} ∀ i, j (21)
Accordingly, the number of times a node needs to start up to perform its assigned monitoring is minimized. This Phase is modeled as TSP path. Details of the stocktickerTSP path are shown in Model 3, where the Miller, Tucker, and Zemlin mathematical formulation [START_REF] Laporte | The traveling salesman problem: An overview of exact and approximate algorithms[END_REF] is adopted. The decision variables and parameters are adjusted in Model 3 such as follows.

1) The cities here are the unique VC sets assigned to periods T = {T j , j = 1, . . . , n}, i.e., the unique results from the previous assignment model (Model 2).

Model 3: TSP Problem Parameters

Let C ij = state Transitions ij [START_REF] Andreozzi | On the integration of passive and active network monitoring in grid systems[END_REF]

Decision Variables

Let x ij = 1, if vc j is chosen for monitoring after vc i 0, otherwise

Model Equations

Minimize

n i=0 n j =i,j=1
C ij x ij [START_REF] El-Moukaddem | Maximizing network topology lifetime using mobile node rotation[END_REF] Subject to n i=0,i =j

x ij = 1 ∀ j (25) n j=0,i =j x ij = 1 ∀ i ( 26
)
u i -u j + (n -1)x ij ≤ n -2 i, j = 2, . . . , n, i = j (27) 1 ≤ u i ≤ n -1 i = 2, . . . , n (28)
2) Define a binary decision variable x ij denoting whether vc j is selected in the path after vc i (23). 3) A feasible solution is a path (HP) that passes through each set exactly once ( 25) and ( 26). 4) Number of state transitions of the members of the sets, from active to sleep and vice versa [START_REF] Andreozzi | On the integration of passive and active network monitoring in grid systems[END_REF]. 5) The cost (distance) C ij of moving from one city (VC set) to the next, from vc i to vc j , is the total. 6) the objective is to find the least costly sequence of VCs over the planning horizon (24). 7) Extra variables u i are required for subtour elimination, in the constraints expressed in ( 27) and [START_REF] Sedjelmaci | An accurate security game for low-resource IoT devices[END_REF].

VI. IMPLEMENTATION AND ANALYSIS

A. Problem Resolution and Implementation

Solving the problem starts with Phase I by generating a DODAG and outputs matrix M. Multiple solutions of the VCP are stored in matrix M. Algorithm 1 runs until no more feasible minimal VCs exist. However, for experimentation purposes, it has been shown to suffice to loop any number of times between the range [1.5|T|-3|T|]. This range denotes the required number of VCs (θ ). Analytical simulation is conducted for networks of 50, 100, 150, and 200 nodes with varying numbers of links. Table I shows the characteristics of the corresponding DODAGs, a summary of the results of the three phases for eight different DODAGs, as well as the metrics used for evaluation. DODAGs are constructed such that there is a root (BR) and each node has at least one path toward it. The edges on the DODAGs are constructed by randomly generating (x, y) positions of each node in a unit square (units do not matter in the graph). The distance between every two nodes is measured; if it is less than a certain threshold parameter then the two nodes are connected.

By varying the threshold parameter, in the range [0 -1], the DODAG gets sparser or denser. Fig. 4 shows an example of a DODAG with 100 nodes and a threshold of 0.09, which gives 234 links. Varying the density of the graph affects the number of nodes required to monitor the entire DODAG. Fig. 5 depicts the effect of varying the density of a DODAG, with 100 nodes, on the percentage of monitors. It is evident that the more the number of communication links between the nodes, the more monitors are required.

Throughout the entire set of experiments, it is assumed that the planning horizon T is divided into ten time periods, and that the energy loss E m per monitoring period assigned for v k is 2% of its total energy. Running Phase I with DODAG number 3 in Table I, for example, (DODAG shown in Fig. 4), outputs matrix M which includes 15 different VCs (VC 1 , . . . , VC 15 ). M is the input of the multiobjective GAP in Phase II.

As mentioned in Section III, the model in Phase II a multiobjective mathematical programming (MMP) problem. There are several approaches to solving MMP problems in the literature. This research adopts the ε-constraint method. This is due to its several advantages over its rivals [START_REF] Khalili-Damghani | An integrated multi-objective framework for solving multi-period project selection problems[END_REF]. In the ε-constraint approach, only one objective function is optimized, whereas the others are added to the constraints. Pareto-efficient solutions are achieved by varying the right hand side of the constrained objective functions.

Although it is widely used, the ε-constraint method has its disadvantages. First of all, it is required to calculate the range of every objective function used as a constraint. The usual way is to build a payoff table. It includes the optimal solution for each objective function optimized individually. There is no guarantee that these optimal solutions are indeed nondominated solutions [START_REF] Mavrotas | Effective implementation of the -constraint method in multi-objective mathematical programming problems[END_REF]. Another weak point is that the optimal solution is not guaranteed to be an efficient solution if there are alternative optima. To overcome some of the limitations of the ε-constraint approach, [augmented ε-constraint method (AUGMECON)] [START_REF] Mavrotas | Effective implementation of the -constraint method in multi-objective mathematical programming problems[END_REF] was developed.

AUGMECON guarantees the Pareto-efficiency of the solutions by using lexicographic optimization 1 of the objective functions. Therefore, the AUGMECON method is implemented in this paper. Through using AUGMECON method for Phase II, the output is the scheduled assignment of the VCs over the periods, which is represented by a binary decision variable s ij .

Input to Phase III is the unique VCs assigned to monitoring in Phase II. Output of Phase III is the sequence that minimizes the total number of state transitions of the nodes. The sequence is generated using a dynamic programming implementation of the TSP problem. Fig. 6 shows a comparison between the sequencing of the VCs assigned in Phase II [Fig. 6(a)] on DODAG number 3, and the sequence after solving the TSP Path of Phase III [Fig. 6(b)]. The new sequence reduces the total number of state transitions by 70%.

B. Performance Evaluation

The experiments were performed on a personal computer with 8 gigabite RAM and an Intel Core i7 processor @2.20 gigahertz. Considering the problem formulations presented in Section V, the metrics used for evaluation (shown in Table I) are as follows.

1) Percentage of nodes selected as monitoring nodes.

2) Average residual energy among monitors.

3) Percentage of reduction in the nodes' state transitions. The originality of this paper is mainly in the proper modeling of the defined problem. Modeling the monitor selection problem as VCP in Phase I guarantees optimal monitor placement to cover the entire set of links. Simultaneously, the percentage of deployed monitors is relatively small, (52%-66%, depending on the density of the network). Consequently, it is possible to identify fine-grained performance link metrics, where monitors send passive probes in an end-to-end approach. This leads to reducing the need for active probes; thus less monitoring overhead. In addition, active probes can be used when needed, to check the availability of network parts, where communication has not been established for long times. Moreover, the proposition in Phase II is able to optimally assign monitors to periods with minimum energy consumption, depending on the number of periods (|T|), the energy loss per period (E m ), and the reserved battery per node (Reserved_battery k ). The values of the parameters used for the test instances have been chosen arbitrarily. This is because the main overriding objective of this paper is to 1 Lexicographic optimization is the sequential optimization of multiple objective functions; by optimizing one function and from the pool of alternative optima sequentially optimize the next. It is interesting to emphasize that when the battery dedicated for monitoring is sufficiently large, fewer VCs are assigned to periods and less monitor scheduling is required.

On the other hand, when the Reserved_battery k is relatively small, more VCs are required to monitor the same number of periods and scheduling for minimal energy consumption is critical. Fig. 7 shows the minimum, average, and maximum remaining (residual) battery after monitoring for a network of 50, 100, 150, and 200 nodes. For E m = 2%, the minimum residual battery does not fall below 80% and the average residual battery is between the range [83%-90%]. Also, when the model was tested without running Phase I, all the nodes were assigned to monitoring.

Consequently, the nodes' battery level dropped to the minimum level. Fig. 8, emphasizes the model's capability of monitoring a dense network of 200 nodes with increasing number of links, without depleting the nodes' reserved battery for monitoring. The figure shows that the density of the network grows up to 2463 links and yet the average residual battery is in the range [82%-98%].

The results after solving the TSP path, for the optimal sequencing of the VCs across the time periods, are very promising. The model is both effective and efficient in reducing the state transitions of nodes up to 80%. It is worth mentioning that in some instances, like DODAG number 8 in Table I, the solution from Phase II is already optimum with Proof: The integer programming solution for the VCP includes a nested loop that runs in exactly (1/2)(|V| -1).|V|. This nested loop is analogous to the constraint in (3) in Model 1. The constraint generation algorithm (Algorithm 1) has a constant running time of θ , where θ represents the required number of generated VCs. As mentioned in Section VI, it is noticed from the preliminary experimentation that it is sufficient to set θ in the range [1.5|T|-3|T|]. The BB algorithm is used to solve the VCP. The complexity of BB is lower bounded by the total number of nodes, which is proportional to 2 |V| [START_REF] El-Moukaddem | Maximizing network topology lifetime using mobile node rotation[END_REF]. Hence, Phase I has a total running time of ((1/2)|V| -1).(|V| + θ).2 |V| , i.e., O(2 |V| .|V| 2 ).

As VCP is NP-hard, a lot of research has been conducted to produce efficient approximation algorithms (see [START_REF] Bourgeois | Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms[END_REF], [START_REF] Åstrand | Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks[END_REF]). The work in [START_REF] Mostafa | Distributed monitoring in 6LoWPAN based Internet of Things[END_REF] develops a polynomial-time algorithm that converts the DODAG into a nice-tree decomposition with unity treewidth. Using the algorithm proposed in [START_REF] Mostafa | Distributed monitoring in 6LoWPAN based Internet of Things[END_REF] yields a significant reduction in the complexity of solving VCP on DODAGs. The problem becomes polynomial-time solvable, even though it is run iteratively using a constraint generation algorithm.

It can be seen from Table I that the majority of computations is relatively centered in the multiobjective GAP in Phase II. For example, DODAG number 4 with 100 nodes and 347 links requires around 10 s to reach the optimal solution for the VCP, and less than 1 s for the TSP Path, and 600 s to reach the optimal solution for the multiobjective GAP. The problem of large running time exists for instances having more than 200 nodes and 350 links. The optimum solution is still reachable, albeit slowly. Fortunately, there exist several approximation algorithms for GAP. For instance, [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF] presented a polynomial-time 2-approximation algorithm for GAP.

Lemma 2: Phase II has a total time complexity of O(2 (|M|.|T|) .

(|V| + |M| + |T|)).

Proof: To prepare the coefficients for the communication objective function F 2 as represented in [START_REF] Molnár | Quasi-optimal scheduling algorithm for area coverage in multi-functional sensor networks[END_REF], the solution loops |M| times. Moreover, a loop of |T| times is required to enforce a period to be assigned once, which is represented in [START_REF] Fang | An integrated system for regional environmental monitoring and management based on Internet of Things[END_REF]. Also, to constraint the energy used for monitoring of each node to be less than or equal to the Reserved_battery k the solution loops |V| times [represented in [START_REF] Jara | Interconnection framework for mHealth and remote monitoring based on the Internet of Things[END_REF]]. The number of variables in the GAP is |M|.|T|. Using the BB algorithm for solving the GAP, which is bounded by the total number of variables, gives an overall time complexity for Phase II of O(2 (|M|.|T|) . (|V| + |M| + |T|)).

Lemma 3: Phase III has time complexity of O(2 u .u 2 ). Proof: Although the TSP path is also NP-hard and there are approximation algorithms proposed in the literature (see [START_REF] Jara | The Internet of everything through IPv6: An analysis of challenges, solutions and opportunities[END_REF]), its running time in the proposed model is relatively small. This is due to the fact that the input of Phase III is only the unique VCs assigned to monitor the periods (u) from Phase II. TSP path is solved using Held-Karp dynamic programming algorithm [START_REF] Molnár | Quasi-optimal scheduling algorithm for area coverage in multi-functional sensor networks[END_REF]. There are at most (2 u .u) subproblems, each of which takes linear time (u) to solve. Therefore, the time complexity of Phase III is O(2 u .u 2 ).

VIII. CONCLUSION

In this paper, a three-phase mathematical model was proposed to address the optimized scheduling of the monitoring role in IoT networks. In the first phase, multiple subsets of the nodes that cover the entire graph are generated by solving VCP iteratively; while incorporating a constraint generation algorithm. The optimized scheduling of the VCs is handled in Phases II and III. The multiple VCs are input to Phase II which is modeled as a multiobjective GAP. The objectives are to minimize the energy and communication costs incurred while monitoring the network. Input to Phase III is the unique VCs assigned to monitoring in Phase II. Phase III is a TSP problem with the objective of further minimizing the energy consumption by reducing nodes' state transitions (from active to sleep and vice versa).

The proposed solution is a proof of concept to emphasize that energy-efficient solutions for monitoring IoT networks do exist. The proposed model and solution method were tested on a number of test instances of different sizes, ranging from 50 to 200 nodes, and from 123 to 2463 links. Experimental results show that, for the sizes of the tested instances, the proposed model was indeed effective and scalable in achieving the monitoring objective, while providing load balancing between monitors and minimizing the cost of monitoring in terms of energy and communication costs, and the number of nodes' state transitions. Future work will be the development of heuristics and approximation algorithms to reduce the complexity of Phase II, since it was noticed to be the most time consuming phase. Often in IoT, the underlying network can change dynamically (nodes, links, topology, etc.), in order to handle these changes, it will be interesting to develop incremental methods and dynamic algorithms for the system control (including the monitoring). To test the energy consumed for transmission of monitoring probes by the nodes, a network simulator should be used. Therefore, testing the proposed model on Cooja network simulator is another possible future work.

Fig. 1 .

 1 Fig. 1. Energy model. (a) Before active time periods merged and (b) After active time periods merged [10].

Fig. 2 .

 2 Fig. 2. Phases of the monitoring optimization.

Fig. 3 .

 3 Fig. 3. Assignment of VCs i to periods j.

F 1 :

 1 Total

Fig. 4 .

 4 Fig. 4. DODAG of a network with 100 nodes and 234 links. Node number 1 is the root.

Fig. 5 .

 5 Fig. 5. Effect of varying the density of the DODAG on the percentage of monitors.

Fig. 6 .

 6 Fig. 6. Assignment of VCs. (a) Before TSP and (b) after TSP.

Fig. 7 .

 7 Fig. 7. Residual battery after monitoring for different-sized networks.

Fig. 8 . 1 )

 81 Fig. 8. residual battery after monitoring for a network of 200 nodes and varying number of links.

) h k

 h Number of hops travelled from each v k in vc i to the root of the DODAG

	H i Total number of hops travelled by all
		v k in vc i
		=	y ki * h k ∀ k ∈ V	(13)
	E m	Energy loss per each monitoring
		period assigned for v k
	Reserved_battery k Maximum battery allowed for
		monitoring
	Decision Variables:

TABLE I SUMMARY

 I OF EXPERIMENTAL RESULTS |T| = 10, E m = 2%, RESERVED_BATTERY k = 50%, INITIAL_BATTERY k = 100

ACKNOWLEDGMENT

Author B. Mostafa would like to thank the L'Oréal foundation and UNESCO for their support by granting her the 2017 L'Oréal-UNESCO for Women in Science Levant and Egypt Fellowship.

This work was supported in part by the Academy of Scientific Research and Technology and in part by the French Ministry of Foreign Affairs for Granting the Imhotep Project MONIOT under Grant 33124VJ.

Basma