Owing to the environmental impact and potential economic benefits, there is an urgent request for green techniques to reduce energy consumption in telecommunication networks. However, green approaches impose signalling overhead on the network. While most research works in the literature focus on minimisation of energy consumption in green networks, the signalling overhead has largely been unexplored. In this work, the authors tackle the trade‐off between energy efficiency and signalling overhead in green routing by formulating an optimisation problem as an integer linear programme (ILP). Their ILP problem minimises signalling overhead with a constraint on the total power consumption of the network. Moreover, their problem introduces the multipath routing feature and takes the flow table sizes of the forwarding devices into account. They prove that the proposed green routing problem is nondeterministic polynomial (NP)‐hard and thus propose a polynomial‐time heuristic algorithm in addition to analysing its time complexity. They evaluate the performance of the heuristic algorithm by comparing its results with those generated by ILP.

Abstract We study the minimum diameter spanning tree problem under the reload cost model (Diameter‐Treefor short) introduced by Wirth and Steffan. In this problem, given an undirected edge‐colored graphG, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree ofGof minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of theDiameter‐Treeproblem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Δ of the input graph. We prove thatDiameter‐Treeispara‐NP‐hard for any combination of two of these three parameters, and that it isFPTparameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we proveDiameter‐Treeto beNP‐hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan proved that the problem can be solved in polynomial time on graphs with Δ = 3, and Galbiati proved that it isNP‐hard if Δ = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem isNP‐hard if Δ = 3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove thatDiameter‐Treeis inXPandW[1]‐hard parameterized by the treewidth plus Δ.

The problem of inefficient and unevenly distributed spectrum usage in industrial wireless networks has led to the emergence of the concept of industrial cognitive radio (CR) networks, which have particularly important applications in automotive industry. Industrial CR networks are planned to function in a wide spectrum range; therefore, they have high energy consumption because of frequency switching while other wireless technologies do not have this problem. A distinctive feature of this switching cost is that it depends on the wideness between the two frequency bands. In this article, we formulate the joint frequency assignment and scheduling problem for multihop industrial CR networks with a single transceiver by considering varying amounts of energy consumption that occurs while CR devices switch to different frequency bands. Our optimization problem, which we formulate as an integer linear program, minimizes the energy cost related to frequency switching while making frequency and time slot allocation to the cognitive devices. We prove that even on star graphs, our formulated problem is inapproximable within any polynomial-time computable function f(n) in addition to being NP-Hard in the strong sense. Therefore, we propose a polynomial-time heuristic algorithm to solve the energy consumption problem due to channel switching. Simulation results demonstrate that the performance of our heuristic algorithm is very close to the results obtained from the integer linear programming implementation by CPLEX optimization software. We also compare our proposed method with the corresponding constant energy consumption for frequency switching case and two state-of-the-art algorithms and demonstrate that taking into account the different energy consumption while switching to different frequency bands is vital for joint frequency assignment and scheduling in multihop industrial CR networks with a single transceiver.

Although green networking and fairness are both vital and rapidly increasing areas of research, providing energy‐fairness in multi‐domain green networks is a hitherto unexplored issue. In this study, the authors address energy‐fair routing in multi‐domain green networks by formulating an optimisation problem as an integer linear programme. The authors' problem maximises the energy saving of the domain with minimum energy saving while ensuring that the energy consumption of each domain is below a given threshold. The model they have established in this study also provides a flexible bandwidth assignment mechanism which improves the feasibility performance of their methods. They then propose a polynomial‐time heuristic algorithm for this problem. They evaluate the performance of their heuristic algorithm by comparison with the results obtained from their integer linear programming formulation using optimisation software CPLEX. The simulation results demonstrate that the heuristic algorithm yields close results to the values obtained from the CPLEX implementation of their proposed formulation in terms of energy‐fairness and outperforms the previous results while at the same time having low computational complexity.

Abstract The reload cost refers to the cost that occurs along a path on an edge‐colored graph when it traverses an internal vertex between two edges of different colors. Galbiati et al. introduced the Minimum Reload Cost Cycle Cover problem, which is to find a set of vertex‐disjoint cycles spanning all vertices with minimum reload cost. They proved that this problem is strongly NP‐hard and not approximable within 1/ϵ for any ϵ > 0 even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. In this paper, we prove that the minimum reload cost is zero on complete graphs with n vertices and an equitable 2‐edge‐coloring except possibly n = 4 or with a nearly equitable 2‐edge‐coloring except possibly for n ≤ 13. Furthermore, we provide a polynomial‐time algorithm that constructs a monochromatic cycle cover in complete graphs Kn with an equitable 2‐edge‐coloring except possibly for n = 4. This algorithm also finds a monochromatic cycle cover in complete graphs with a nearly equitable 2‐edge‐coloring except for some special cases.

Abstract In an edge‐colored graph, a traversal cost occurs along a path when consecutive edges with different colors are traversed. The value of the traversal cost depends only on the colors of the edges. Two related global cost measures, namely the reload cost and the changeover cost with applications in telecommunications, transportation networks, and energy distribution networks have been studied in the literature. Previous work focused on problems with an edge‐colored graph being part of the input. In this paper, we formulate problems that aim to find an edge coloring of a graph minimizing the reload and changeover costs. One pair of problems aims to find a proper edge coloring to minimize the reload/changeover cost of a set of paths. Another pair of problems aim to find a proper edge coloring and a spanning tree to minimize the reload/changeover cost. We present several hardness results and polynomial‐time solvable special cases.

Cash-related costs constitute a large portion of management cost of an automated teller machine (ATM) network. Cash should be delivered to or picked-up from ATM devices in certain intervals in order to both meet customer satisfaction and to be able to generate additional revenue from excess cash through daily interest rates. Unlike classical ATMs, new-generation ATMs, also called recycle ATMs, have a single cassette for cash withdrawal and deposit; this property imposes new restrictions on ATM cash management. Moreover, recycle ATMs are costly, and hence their deployment should be planned carefully. In this paper, our aim is to optimize the ATM networks in terms of cash related costs. We formulate an optimization problem as an integer linear program, which jointly decides on when to visit an ATM, how much money to deliver to which ATM and which road should be followed for the distribution of cash to the ATMs. We also decide on which ATMs in the network should be replaced by a recycle ATM. We then propose a polynomial-time heuristic algorithm and compare it with the optimization formulation in terms of cash cost and the recycle ATM decision. We demonstrate through performance evaluation that our heuristic algorithm is suitable for practical implementation.

We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that DIAMETER-TREE is para-np-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with Delta=3, and Galbiati (2008) proved that it is NP-hard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta=3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus Delta.

Virtual network operators may distrust each other and require that their virtual infrastructure is not cohosted on the same physical equipment. In this paper, we formulate a virtual network embedding problem that maximizes the total revenue where conflicting virtual network operators utilize distinct physical devices. Virtual links in our model have the option of selecting among a range of discrete bandwidth values, which have a corresponding price. This way, any revenue function can be realized. We evaluate the performance of our model by comparing it with a fixed bandwidth scheme and demonstrate its superior performance in terms of revenue.

Research studies show that energy consumption in communication networks is mainly related to active network elements such as communication links. Based on this approach, several energy management techniques, generally known as green techniques, have been proposed. Their main goal is to minimize energy consumption by routing network traffic through a set of network resources and powering off the remaining unused resources. However, this approach imposes a signaling overhead on the routing system due to selectively powering off/on the network resources. In this work, we investigate the trade-off between energy efficiency and signaling overhead in a software defined network (SDN) domain with a single controller. To this end, we formulate an integer linear programming (ILP) problem whose objective function is to minimize the control overhead by taking into account the total energy consumption of the network. We then propose two polynomial-time heuristic algorithms to find near-optimal solutions for the problem. We evaluate the performance of our heuristic algorithms by comparison with the results obtained from our ILP formulation using optimization software CPLEX.

We focus on throughput-maximizing, max-min fair, and proportionally fair scheduling problems for centralized cognitive radio networks. First, we propose a polynomial-time algorithm for the throughput-maximizing scheduling problem. We then elaborate on certain special cases of this problem and explore their combinatorial properties. Second, we prove that the max-min fair scheduling problem is NP-Hard in the strong sense. We also prove that the problem cannot be approximated within any constant factor better than 2 unless P=NP. Additionally, we propose an approximation algorithm for the max-min fair scheduling problem with approximation ratio depending on the ratio of the maximum possible data rate to the minimum possible data rate of a secondary users. We then focus on the combinatorial properties of certain special cases and investigate their relation with various problems such as the multiple-knapsack, matching, terminal assignment, and Santa Claus problems. We then prove that the proportionally fair scheduling problem is NP-Hard in the strong sense and inapproximable within any additive constant less than log(4/3). Finally, we evaluate the performance of our approximation algorithm for the max-min fair scheduling problem via simulations. This approach sheds light on the complexity and combinatorial properties of these scheduling problems, which have high practical importance in centralized cognitive radio networks.

We formulate a scheduling problem that takes into account different hardware delays experienced by the secondary users (SUs) in a centralized cognitive radio network (CRN) while switching to different frequency bands. We propose a polynomial-time suboptimal algorithm to address our formulated scheduling problem. We evaluate the impact of varying switching delay, number of frequencies, and number of SUs. Our simulation results indicate that our proposed algorithm is robust to changes in the hardware spectrum switching delay and its performance is very close to its upper bound. We also compare our proposed method with the corresponding constant switching delay-based algorithm and demonstrate that our suggestion of taking into account the different hardware delays while switching to different frequency bands is essential for scheduling in CRNs.

In this paper, we propose an interference aware throughput maximizing scheduler for cognitive radio networks (CRNs) as part of a MAC layer resource allocation framework. In the considered CRN scenario, the cognitive users with multiple antennas are coordinated by a centralized cognitive base station. We evaluate the performance of our proposed scheme using analysis of variation (ANOVA) technique. We also show experimental results for the total throughput for varying number of cognitive users and frequencies.

The work presented in this paper1 focuses on a new approach in provisioning Quality of Service (QoS) in ad hoc wireless networks, aiming at making the best use of ad hoc networking as a candidate technology for next generation wireless networks. Specifically, a cross-layer QoS provisioning architecture for wireless ad hoc networks is introduced and described, based on the integration of the recently proposed service vector concept at the network layer and a delay bounded power efficient scheduling at the data link layer. It is demonstrated through modeling and simulations that this novel architecture can provide considerable performance improvements in terms of both power savings and enhanced QoS granularity in wireless ad hoc networks. Furthermore, the performance of the proposed scheme under various traffic arrival rates and distributions is evaluated.

Abstract Emerging real‐time communications and multimedia applications necessitate the provisioning of Quality of Service (QoS) in Internet. Recently, a new concept, referred to asservice vector, has been introduced to enhance the end‐to‐end QoS granularity, and at the same time, maintain the simplicity and scalability feature of the current differentiated services (DiffServ) networks. This work extends this concept to wireless ad hoc networks and proposes a cross‐layer architecture based on the combination of delay‐bounded wireless link level scheduling and the network layer service vector concept, resulting in significant power savings and finer end‐to‐end QoS granularity. The impact of various traffic arrival distributions and flows with different QoS requirements on the performance of this cross‐layer architecture is also investigated and evaluated. Copyright © 2006 John Wiley & Sons, Ltd.