On-demand charging of sensor nodes (SNs) in wireless rechargeable sensor networks has garnered immense attention. Existing works with multiple mobile chargers (MCs) overlooked the benefits of partial charging and distributed control in large-scale wireless rechargeable sensor networks. In addition, most of them have not considered the complete heterogeneity of SNs’ energy profiles and idleness of the MCs. In this article, we address the aforesaid issues and present a game theory based distributed mobile charging protocol, called DMCP. We formulate the mobile charging problem as a series of repeated games played among the MCs and represent a game as a 0-1 integer linear programming to maximize the total profit of the MCs. In each game, DMCP dynamically determines the factor of charging of the energy-deficit SNs based on their relative criticality and selects the next-to-be-recharged SNs using an efficient bi-objective payoff function. In addition, it utilizes an innovative strategy and a self-enforcing agreement to promote cooperation among the MCs. Through extensive simulations and hypothesis testing, we show that DMCP reduces the charging delay up to 44.04% and enhances the charging coverage and survival rate up to 45.12% and 49.97%, respectively.

We exploit spatiotemporal correlation in sensor data and redundant binary number system based representation for encoding data, where the number of 0 s in the encoded data is significantly larger than the other symbols. Next, using a hybrid FSK-ASK modulation/demodulation technique with a non-coherent receiver, we have designed an energy-efficient communication scheme where the transmitter is kept silent during the transmission of the dominant symbol in the encoded messages. In contrast to the conventional techniques of data reduction and aggregation which exploit temporal and spatial correlation, our technique does not require dropping any data value while generating significantly more transmission energy savings. Our approach is particularly useful for sustainable energy-efficient communications in IoT applications like environment monitoring, agriculture, etc., where dropping any data value may not be desirable. Simulation results on different real-life sensor data sets using several popular low-cost, low data-rate transceivers like the RFM TR 1,000 show about$90.06\% - 90.86\%$savings in transmitter energy expenditure over conventional BFSK, and$15\% - 20\%$savings at receiver. Simulation results also demonstrate a proportionately reduced$CO_{2}$footprint generation of$0.12 - 0.14$mg/day only, when using the RFM TR 1,000 radio. These savings are considerably higher than those generated with the existing techniques.

In a natural disaster, when there is a sudden rush in vehicle movement from dense residential areas of a city towards some designated evacuation centers, traffic needs to be distributed along the road network in an optimal way so as to minimize the travel time for reaching those evacuation centers. We address this traffic distribution problem in a$k \times k$Manhattan road network with multiple traffic generating sources and a single fixed destination (sink) at a corner point. We first consider queuing delay at each grid point along with a fixed link delay. We then extend our idea to consider a rectangular grid and also real-life road networks where some of the links may be absent. We present a traffic distribution algorithm that would minimize the average time of all vehicles to reach the given destination point. Simulation of our algorithm using SUMO on the grid-structured road map of Manhattan borough in New York city and also on a part of non-grid road map of city of Carbondale, IL USA shows a much shorter average travel time compared to the existing popular algorithms based on dynamic traffic assignments (DTA). The proposed technique is also robust in the sense that even with 20% deviation from optimal assignment of traffic distribution at cross-points, we get significantly better results compared to the existing traffic distribution policies. We then propose a congestion control technique based on detouring of vehicles and show how variable link delay as a function of the volume of traffic flow through a link can be incorporated in our traffic distribution policy. Finally, we show how to extend our technique to consider a scenario with the destination point being anywhere on the grid, instead of being at the corner point.

We address the problem of evacuation of people in a natural disaster or some other emergency situations. In such a scenario, traffic from different parts of a city start moving simultaneously towards the nearest safe location. We propose here an optimal traffic routing algorithm in an 'almost' grid-structured network in a city to reach the safe location in minimum time, which is based on a novel technique of successively partitioning the network in suitable sub-networks to tackle the issue of missing links in the grid. Simulation results with the road network of Manhattan city show that our proposed technique performs better in terms of average time to reach the evacuation center than any of the existing techniques.

Channel assignment problem in hexagonal cellular networks for multimedia services in a 2-band buffering environment is addressed here. We consider the simplest case of only two types of multimedia services, each having different bandwidths. We first derive lower bounds under different conditions on the minimum bandwidth requirement for assigning multimedia channels to a seven-node subgraph of the hexagonal cellular network by using a novel technique where assignment of different types of signals to support multimedia services are interleaved in the assignment process for the minimum bandwidth. We next propose a multimedia channel assignment algorithm to satisfy the non-homogeneous demands at each node of the network. To evaluate the performance of our proposed algorithm, we present new benchmark instances for multimedia communication. Our proposed algorithm, when run on different benchmark instances, comes up with assignments which require a minimum of 7 percent and a maximum of 40 percent more bandwidth than their corresponding lower bounds. The execution time for all the modified Philadelphia benchmark instances defined on a 21-node network is always within 265 milliseconds on an HPxw8400 workstation, while that for the modified benchmark instances defined on a 55-node network is within 733 milliseconds.

In this paper, an energy-efficient communication scheme for low-power wireless networks is proposed which is based on encoding the messages by a novel source coding technique, called Dual-message Compression with Variable Null Symbol (DGVNS), followed by using the concept of Silent Communication. The source coding technique used in this scheme interleaves bits from two messages and encodes every two consecutive bits of this interleaved dual-message by one of four symbol values so that the overall message length is reduced by a factor of two. The transmitter is kept silent during the periods of the most dominant symbol which is dynamically changed. A hybrid modulation / demodulation technique using non-coherent FSK and ASK is used to have 43.46% energy savings on an average at the transmitter using a channel with Additive White Gaussian Noise (AWGN), and 50% energy savings at the receiver over the conventional Binary Frequency Shift Keying (BFSK), with equal likelihood of all possible strings of binary messages. Simulation results with real-life sensor data show that we can get still higher energy savings at the transmitter, ranging from about 54.1% to 58.9%. Also, the transmission time is reduced by a factor of two due to the reduced length of the encoded message. The scheme is suitable for multihop communication in low cost wireless sensor network applications.

We address the problem of optimally placing the access points in an ultra-dense 5G network to cover a given rectangular region so that every point in the region will be covered by at least one access point (AP) with minimal sum of total transmission power used by all APs. We analyze the wastage of transmission power for different types of placement of the APs with touching and intersecting circles for the full coverage of the rectangular region. We show that the minimum wastages in the inner bulk region with touching and intersecting circles are 81.4% and 20.77%, respectively. We then propose a systematic scheme to place the intersecting circles and show that for moderate size of the rectangle, the wastage due to the spill over of the circles at the boundary can be much higher that 20.77%, but when the side(s) of the rectangle is(are) very large compared to the radius r of the circles, the wastage asymptotically tends to around 20.86%. Also, we show that use of a few circles of smaller radius r' = 0.62r would significantly reduce the wastage even for a rectangle of small size and that would not require any additional bandwidth compared to the scheme for using all circles of the same radius r. The proposed placement scheme is very simple, elegant and effective in minimizing wastage of transmission power of APs as well as optimizing the bandwidth requirement through reuse of channels avoiding co-channel and adjacent channel interferences.

A significant number of applications in mobile transactions and wireless sensor networks (WSNs) are characterized by short duration sessions. Stream ciphers are a popular choice for ensuring the security of data communication sessions in such applications. In this paper, we propose a lightweight variant of the popular RC4 algorithm that is highly suitable for energy and computational resource constrained devices in wireless networks, as compared to RC4 and its variants (e.g., HC-128), Grain-128, etc., while being secure enough for a large class of short duration wireless application scenarios. We replace the PRGA keystream generation algorithm of RC4 by our proposed Lightweight Pseudo-Random Generation Algorithm (LPRGA). The test results for LPRGA on the NIST statistical test suite show that the output keystream generated by LPRGA is as random as the output generated by the PRGA of RC4, for keystream sequence lengths smaller than 30,000 bits - a requirement easily satisfied in nearly all mobile transactions, WSNs and ad hoc networks. The structural test results also prove the security strength of the proposed LPRGA. Furthermore, measurements of the period lengths of the LPRGA show that the proposed algorithm has a much larger period than the PRGA of RC4. We have also proved analytically the unpredictability of the proposed algorithm. Finally, for resource constrained wireless devices, we present the outline of a high performance hardware implementation with a significantly lower cost as compared to the conventional hardware implementations of RC4 for wireless networks. Our proposed hardware implementation is capable of throughput as high as one cipher byte per cycle of a 1 GHz clock using 65 nm fabrication technology.

RC4 is the most popular stream cipher in the domain of cryptology. In this paper, we present a systematic study of the hardware implementation of RC4, and propose the fastest known architecture for the cipher. We combine the ideas of hardware pipeline and loop unrolling to design an architecture that produces 2 RC4 keystream bytes per clock cycle. We have optimized and implemented our proposed design using VHDL description, synthesized with 130, 90, and 65 nm fabrication technologies at clock frequencies 625 MHz, 1.37 GHz, and 1.92 GHz, respectively, to obtain a final RC4 keystream throughput of 10, 21.92, and 30.72 Gbps in the respective technologies.

This paper presents a novel method for solving channel assignment problems (CAPs) in hexagonal cellular networks with nonhomogeneous demands in a 2-band buffering system (where channel interference does not extend beyond two cells). The CAP with nonhomogeneous demand is first partitioned into a sequence of smaller subproblems, each of which has a homogeneous demand from a subset of the nodes of the original network. Solution to such a subproblem constitutes an assignment phase, where multiple homogeneous demands are assigned to the nodes corresponding to the subproblem, satisfying all the frequency separation constraints. The whole assignment process for the original network consists of a succession of multiple homogeneous assignments for all the subproblems. Based on this concept, we present a polynomial time approximation algorithm for solving the CAP for cellular networks having nonhomogeneous demands. Our proposed assignment algorithm, when executed on well-known benchmark instances, comes up with an assignment which is always within about 6 percent more than the optimal bandwidth, but requires a very small execution time (less than 5 millisecond on a HPxw8400 workstation). The proposed algorithm is very much suitable for real-life situations, where fast channel assignment is of primary importance, tolerating, however, a marginal deviation (6 percent) from the optimal bandwidth.

We propose a novel scheme for multi-path routing in a Cognitive Radio Network (CRN) for multimedia communication, even when a contiguous band of required width is not available for any hop in the route. The proposed scheme is based on an extension of the idea of Sample Division Multiplexing (SDM) as given in [1] for single-hop communication. Starting from the source node, we first explore the available (free) number of channels (not necessarily contiguous) between every pair of 1-distance neighbor nodes by the help of appropriate control messages. With the information gathered from this step, the network graph G is constructed. We run the max-flow algorithm [8] on this network graph to find the set of routes between the source and the destination nodes so that the sum total of the usable numbers of channels through all these routes is equal to the required number of channels for the multimedia signal to be communicated. In essence, each data packet of the multimedia signal is split into several sub-packets following the basic concept given in [1] each of which needs much smaller bandwidth than the original packet, and these sub-packets are sent through all these routes to be eventually received by the destination node with the desired QoS. The time complexity of our proposed algorithm for this route discovery is O(pf + TSD), where p is the number of edges in the network graph (G), f is the maximum flow in G and TSDis the initialization time for constructing the network graph. We have shown that TSDis O(Δδmax), where Δ is the diameter and δmaxis the maximum node degree of the network graph.

We propose a redundant radix based number (RBN) representation for encoding and transmitting data for applications which typically utilize low cost devices and demand low power operations with simple modulation techniques like ASK, OOK and FSK. Coupled with silent periods for communicating the digit zero, this encoded communication scheme, called as RBNSiZeComm, provides a highly energy-efficient technique for data transmission. Considering an n-bit data representation and assuming that each of the 2nbinary strings is equally likely to occur, theoretically obtainable fraction of energy savings by using our proposed RBNSiZeComm transmission protocol is, on an average, 1 - n+2/4n. A hybrid modulation scheme using FSK and ASK with non-coherent detection based receiver for the RBNSiZeComm protocol has been presented. Assuming equal likelihood of all possible binary strings of a given length, there is nearly 53% savings in energy on an average at the transmitter relative to binary FSK, over additive white gaussian noise (AWGN) channels. Simulation results demonstrate that compared to binary FSK, our proposed implementation can extend the battery life of devices from about 33% to 62% on an average in applications like remote healthcare and wireless sensor networks for agriculture.

Abstract Efficient allocation of channels for wireless communication in different network scenarios has become an extremely important topic of recent research. The main challenge lies in the fact that the channel allocation problem is NP‐complete. Because of a maximum allowable time limit imposed in practical situations for allocation of channels, sometimes we may need to be satisfied with a near‐optimal solution. In this correspondence, we present a discussion on the various challenges and approaches that have been used by different researchers to solve the problem of channel allocation taking into account different interference issues and efficient utilization of available communication channels for cellular mobile (including multimedia communication) environment and cognitive radio based networks. Copyright © 2010 John Wiley & Sons, Ltd.

Wireless sensor networks typically require low cost devices and low power operations. Hence, such networks usually employ radios with only simple modulation techniques such as ASK, OOK and FSK. We propose a new energy efficient communication scheme for wireless sensor networks that is based on the ternary number system encoding of data. An efficient algorithm for conversion from binary to ternary and vice versa is used that does not involve any division or multiplication but only addition. Our Ternary with Silent Symbol (TSS) communication scheme is similar in concepts to the RBNSiZeComm protocol proposed. However, in contrast to RBNSiZeComm, TSS simultaneously saves energy at both the transmitter and receiver due to shortening of the transmission duration. We also propose a transceiver design that uses a hybrid modulation scheme utilizing FSK and ASK so to keep the cost/complexity of the radio devices low. With a non-coherent detection based receiver and assuming equal likelihood of all possible binary strings of a given length, there is a savings of about 20% in energy on an average at the transmitter compared to binary FSK, for additive white gaussian noise (AWGN) channels. Simultaneously, there is a savings of 36.9% at the receiver too, due to the reduced length of ternary encoded transmitted data, compared to binary encoding. Coupled with the low cost and low complexity of the transceiver, these results establish the effectiveness of TSS as a suitable candidate for communication in low power wireless sensor networks.

A cellular network is often modelled as a graph and the channel assignment problem is formulated as a coloring problem of the graph. Sen et al. (1998) introduced the notion of cellular graphs that models the hexagonal cell structure of a cellular network. Assuming a k-band buffering system where the interference does not extend beyond k cells away from the call originating cell, we provided two different formulations of the channel assignment problem: distance-k chromatic number problem and k-band chromatic bandwidth problem. The channel assignment algorithms presented in Sen et al. were non-optimal. In this paper we provide: (i) a new algorithm for the distance-k chromatic number problem that is optimal and (ii) a near optimal algorithm for the 2-band chromatic bandwidth problem that has a performance bound of 4/3. The complexity of the algorithms is O(p), where p is the number of cells.

This paper introduces a new network topology, called Multi-Mesh (MM), which uses multiple meshes as the basic building blocks interconnected in a suitable manner. The proposed network consists of n/sup 4/ processors and is 4-regular with a diameter of 2n. The network also contains a Hamiltonian cycle. Simple routing algorithms for point-to-point communication, one-to-all broadcast, and multicast have been described for this network. It is shown that a simple n/sup 2//spl times/n/sup 2/ mesh can also be emulated on this network in O(1) time. Several application examples have been discussed for which this network is found to be more efficient with regard to computational time than the corresponding mesh with the same number of processors. As examples, O(n) time algorithms for finding the sum, average, minimum, and maximum of n/sup 4/ data values, located at n/sup 4/ different processors have been discussed. Time-efficient implementations of algorithms for solving nontrivial problems, e.g., Lagrange's interpolation, matrix transposition, matrix multiplication, and Discrete Fourier Transform (DFT) computation have also been discussed. The time complexity of Lagrange's interpolation on this network is O(n) for n/sup 2/ data points compared to O(n/sup 2/) time on mesh of the same size. Matrix transpose requires O(n/sup 0.5/) time for an n/spl times/n. matrix. The time for multiplying two n/spl times/n matrices is O(n/sup 0.6/) with an AT-cost of O(n/sup 3/). DFT of n sample points can be computed in O(n/sup 0.6/) time on this network. The previous papers show that n/sup 4/ data elements can be sorted on this network in O(n) time.

An efficient complete exchange algorithm is presented for a multi mesh network having N (=n/sup 4/) processors (n=2/sup k/), with wormhole routing as the method of message passing between two communicating processors. The proposed algorithm effectively uses the cycles of length n and 2n respectively, present in the multi mesh topology. The total time required for complete exchange is O(mN/sup 5/4/logN), where m is the message length (assumed to be the same for all the messages).

The shear-sort algorithm on an SIMD mesh model requires 4/spl radic/N+o(/spl radic/N) time for sorting N elements arranged on a /spl radic/N/spl times//spl radic/N mesh. In this paper, we present an algorithm for sorting N elements in time O(N/sup 1/4/) on an SIMD multi-mesh architecture, thereby significantly improving the order of the time complexity. The multi-mesh architecture is built around n/sup 2/ blocks, where each block is an n/spl times/n mesh with n=N/sup 1/4/, so that each processor will uniformly have four neighbors in the final topology.

A new family of interconnection network, called Generalized Hypercube-Connected-Cycle (GHCC), is proposed. The topology is defined with two integer parameters l and m such that the total number of nodes N=lm/sup l/, degree of each node /spl delta/=m+1. The diameter D=[5l/2]-2, when l/spl ges/4, m/spl ne/1 and D=[5l/2]-1 when l/spl les/3 m/spl ne/1. The topology offers a design flexibility in the sense that out of the three design parameters N, /spl delta/ and D, any two can be chosen independently. The network graph is node symmetric, (m+1)-connected and also it provides a simple routing scheme. Implementation of the ASCEND and DESCEND classes of algorithms on this topology has also been described.

A generalized model for faults in multivalued I/sup 2/L circuits has been proposed. Using this model, the test sets have been generated for testing the basic modules of a parallel multiplier using multivalued I/sup 2/L technology. These basic modules include four input balanced ternary full adder and a precarry generator, each of which has multivalued current inputs and outputs. The generated test sets can detect single faults (either 'stuck-at' or 'skew' type) in these circuits.

We propose a scheme for evaluating four commonly used functions namely, (1) inverse trigonometric functions, (2) trigonometric functions, (3) the exponential function, and (4) the logarithmic function with the help of a logarithmic number system (LNS) processor. A novel idea of series folding has been introduced for computing the above functions, expressed in the form of infinite series. We also show that with a suitable choice of the radix for the LNS we can evaluate exponential and logarithmic functions without using any extra hardware.>

The ring network is a popular network topology for implementation in local area networks and other configurations. But it has a disadvantage of high diameter and large communication delay. So loop networks were introduced with fixed-jump links added over the ring. In this paper, we characterize some values for the number of nodes for which the lower bound on the diameter of loop networks is achieved. We also give an O(/spl delta/) time algorithm (where /spl delta/ is the diameter of the graph) for finding a shortest path between any two nodes of a general loop network. We also propose a scheme to find a near optimal path (not more than one over the optimal) in case of a single node or link failure.

We show that by adding eight extra edges, referred to as bridges, to an n-cube (n/spl ges/4) its diameter can be reduced by 2, and by adding sixteen bridges to an n-cube (n/spl ges/6) its diameter can be reduced by 3. We also show that by adding (/sub m+1sup 4m/)+1(m/spl ges/2) bridges to an n-cube (n/spl ges/4m and n/spl ges/8) its diameter can be reduced by 2m and by adding 2(/sub msup 4m-3/)+1, (m>2) to an n-cube (n/spl ges/4m-2 and n/spl ges/10) its diameter can be reduced by 2m-1. We also consider the reduction of diameter of an n-cube by exchanging some independent edges (twisting), where two edges are called independent if they are not incident on a common node. We have shown that by exchanging four pairs of independent edges in a d-cube (d/spl ges/5), we can reduce its diameter by 2. By exchanging sixteen pairs of independent edges, the diameter of a d-cube (d/spl ges/7) can be reduced by 3. By exchanging 57 pairs of independent edges, the diameter can be reduced by 4 for d/spl ges/9. To reduce the diameter by lower bound [d/2], (d/spl ges/10) we need to exchange (/sub r+1sup d-1/) pairs of independent edges, where r=lower bound [d/4]+1.>

Presents an algorithm for parallel multiplication of two n-bit ternary numbers. This algorithm uses the technique of column compression and computes the product in (2 upper bound /spl lsqb/log/sub 2/n/spl rsqb/+2) units of addition time of a single-bit ternary full adder. This algorithm requires regular interconnection between any two types of cells and hence is very suitable for VLSI implementation. The same algorithm is also applicable to the multiplication of negative numbers.>

Two algorithms for parallel multiplication of two n-bit binary numbers are presented. Both use column compression to increase the speed of execution. They require almost regular interconnection between only two types of cells and hence are very suitable for VLSI implementation. Both of them can also be easily modified to handle two's complement numbers with constant differences in time.>

In this correspondence we develop a parallel algorithm to compute the all-pairs shortest paths and the diameter of a given graph. Next, this algorithm is mapped into a suitable VLSI systolic architecture and the performance of this proposed VLSI implementation is evaluated.

The problem of estimating the number of all possible multiple short circuit faults in a network with a given number of lines is settled in this correspondence. A new combinatorial number, namely an associated Bell number B'(r), which enumerates the number of possible partitions of a set {1, 2,···, r} with certain constraints, is introduced. This concept immediately resolves the counting problem of short-circuit or bridging faults in an electrical network. A related combinatorial problem is also discussed which shows that under some realistic model of circuit failure, the number of possible ways the network can malfunction is closely connected to the Fibonacci sequence.