Radio frequency identification (RFID) has been widely used in many fields such as object tracking and inventory management. For RFID systems, grouping is a fundamental issue which can support efficient multicast transmissions, dynamic tag management, and accurate aggregate queries. Existing grouping protocols have drawbacks of unknown theoretical communication time, high computational cost on the server end and inability to deal with unexpected tags which are those tags whose IDs have not been collected by readers. In this paper, we would like to address the above limitations and consider a more general grouping problem that allows an arbitrary number of unexpected tags to present. Our objective is to design a protocol that guarantees the reader to efficiently and correctly notify each known tag of its group-ID, while the probability that an unexpected tag is mistakenly notified of any group-ID is smaller than a pre-determined value. In this paper, we first obtain a lower bound on the communication time for solving this generalized grouping problem. Then, we propose a near-optimal protocol, called OPT-G, and prove that its communication time approximately equals the lower bound. Finally, we report extensive simulation results that demonstrate OPT-G's near-optimal performance and its superiority over existing baseline schemes.

This paper firstly proposes a greedy online packet scheduling algorithm for the problem raised by Mao, Koksal and Shroff that allows arbitrary hard deadlines in multi-hop networks aiming at maximizing the total revenue. With the same assumption of$\rho _{M} / \rho _{m}={O}(1)$where$\rho _{M}$and$\rho _{\textit {}m}$are the maximum and minimum revenue a packet may carry, our algorithm is${O}$(${P} _{M}$)-competitive improving on MKS algorithm by a factor of${O}$(log${P} _{M}$), where${P} _{M}$is the length of the longest path a packet may travel in the network. We prove that it is asymptotically optimal by presenting a lower bound of${P} _{M}$on the competitiveness for this problem. Secondly, this paper studies the extension of this problem that includes routing as a part of the solution. We prove that using the fastest path algorithm for the routing part, the greedy online algorithm also achieves asymptotically optimal competitiveness for the extended problem. Furthermore, we present a non-greedy online algorithm that not only is asymptotically optimal, but also can adaptively achieve a better competitiveness when the network has a larger${C} _{\textit {min}}$, where${C} _{\textit {min}}$is the minimum link capacity in the network. Finally, simulation results are reported, showing that not only do the greedy online algorithms achieve asymptotically optimal bounds, but also practically achieve better performance than the previously proposed algorithms.

Along with Network Function Virtualization (NFV), Mobile Edge Computing (MEC) is becoming a new computing paradigm that enables accommodating innovative applications and services with stringent response delay and resource requirements, including autonomous vehicles and augmented reality. Provisioning reliable network services for users is the top priority of most network service providers, as unreliable services or severe service failures can result in tremendous losses of users, particularly for their mission-critical applications. In this paper, we study reliability-aware VNF instances provisioning in an MEC, where different users request different network services with different reliability requirements through paying their requested services with the aim to maximize the network throughput. To this end, we first formulate a novel reliability-aware VNF instance placement problem by provisioning primary and secondary VNF instances at different cloudlets in MEC for each user while meeting the specified reliability requirement of the user request. We then show that the problem is NP-hard and formulate an Integer Linear Programming (ILP) solution. Due to the NP-hardness of the problem, we instead devise an approximation algorithm with a logarithmic approximation ratio for the problem. Moreover, we also consider two special cases of the problem. For one special case where each request only requests one primary and one secondary VNF instances, the problem is still NP-hard, and we devise a constant approximation algorithm for it. For another special case where different VNFs have the same amounts of computing resource demands, we show that it is polynomial-time solvable by developing a dynamic programming solution for it. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and the empirical results of the algorithms outperform their analytical counterparts as theoretical estimations usually are very conservative.

Radiative wireless power transfer (WPT) is a promising technique to power wireless devices' transmission. In a resource-limited device, receiving energy and transmitting data cannot operate at the same time because they share the same spectrum or hardware. This paper studies the problem for a wireless device to decide when to harvest energy, when to deliver data, and what transmission rate to use. Distinct from the most existing works, we focus on delay minimization in transmitting a sequence of data packets over a point-to-point channel, which is critical for time-sensitive applications. Since the battery is capacitated, the device must repeatedly switch between harvesting energy and transmitting data. For the offline case where packet information is known before scheduling, a surprising result is discovered that for all (energy receiving and data transmitting) cycles, except the last one, the optimal transmission rate should be a constant which is called the wOPT rate. Based on this discovery, the offline delay minimization problem is optimally solved. For the online case where packets arrive dynamically without prior information, we propose a simple online algorithm: using the wOPT rate to transmit whenever both energy and data are ready. It is proved to be 1.16-competitive if the battery is initially empty, namely, its delay is less than 1.16 times the offline optimal delay for any given packet set. When the battery is with arbitrary initial energy, simulation results show that the performance is near optimal. The discovery of the wOPT rate reveals an essential property of WPT and is expected to be significant in solving other related problems.

Recently, personality detection based on texts from online social networks has attracted more and more attentions. However, most related models are based on letter, word or phrase, which is not sufficient to get good results. In this paper, we present our preliminary but interesting and useful research results to show that the structure of texts can be also an important feature in the study of personality detection from texts. We propose a model named 2CLSTM, which is a bidirectional LSTMs (Long Short Term Memory networks) concatenated with CNN (Convolutional Neural Network), to detect user's personality using structures of texts. Besides, a concept, Latent Sentence Group (LSG), is put forward to express the abstract feature combination based on closely connected sentences and we use our model to capture it. To the best of our knowledge, most related works only conducted their experiments on one data set, which may not well explain the versatility of their models. We implement our evaluations on two different kinds of datasets, containing long texts and short texts. Evaluations on both datasets have achieved better results, which demonstrate that our model can efficiently learn valid text structure features to accomplish the task.

Wireless power transfer (WPT) is a recently developed technique to perfectly address the energy problem for smart city sensors that do not have a readily wired power supply. In a radio-frequency-powered wireless communication system, sensors first harvest energy via the radio-frequency WPT, and then, transmit sensed data to the receiver. The “harvest-then-transmit” protocol is used to coordinate the two operations, in which we wish to optimally decide when to harvest energy, when to transmit data, and what transmission rate should be used such that the data are maximally transmitted. Unlike existing works, we assumed that the wireless transferred power is dynamically changing, instead of being constant, which is more realistic in green smart city applications, e.g., Industry 4.0 workshop, smart transportation, and smart buildings, where environments are continuously changing, so the wireless transferred power is affected dynamically. In this paper, we present an optimal scheduling algorithm for the offline case where the varying WPT is known in advance. Based on the optimal principles learned from the offline case, we have designed an efficient online algorithm. Finally, we report our simulation results that demonstrate that our online scheduling algorithm can adaptively and efficiently achieve high data throughput.

Wireless power transfer (WPT) technique enables wireless charging/recharging, thus is a promising way to power wireless devices' transmissions. Because current WPT technique requires a wireless device to stop transmitting data when receiving power, and also because the received power in this way is limited, careful scheduling is needed to decide when the device should receive power and when it should transmit such that data can be efficiently transmitted. This paper assumes the most fundamental point-to-point White Gaussian Noise channel is used for data transmission and attempts to obtain an optimal scheduling such that a sequence of data packets can be transmitted with the minimum delay. It is discovered that, for all (energy receiving, data transmitting) cycles, except the last one, the optimal transmission rate should be a constant which is called the wOPT rate. Based on this discovery, this paper optimally solves the offline delay minimization problem. Then, an online heuristic scheduling algorithm is proposed, which either receives energy or transmits at the wOPT rate. Simulations have demonstrated its efficiency. The discovery of the wOPT rate reveals an essential property of WPT, thus is expected to make significant impact in the field of WPT.

This paper presents an optimal rate scheduling algorithm called Truncation for an energy-harvesting enabled wireless transmitter to transmit a set of dynamically arrived packets with minimum transmission energy. Distinct from existing works, we allow packets to have individual delay constraints, which is the most general model ever assumed but is very much desired to guarantee per-application quality-of-service (QoS). Moreover, we restrict the allowable rates to a set of discrete values, which is more practical and required in many real applications. As the first achievement, we obtain an optimal offline algorithm, which assumes the rate is continuously adjustable. Then, we propose a general framework that transforms any algorithm using the continuous-rate model into an algorithm using only discrete-rates, while preserving the optimality as long as the optimality holds for convex rate-power functions. It is possible that the harvested energy is insufficient to guarantee all packets to meet their deadlines. Should this occur, maximizing throughput with the limited available energy becomes the goal to achieve. Our Truncation algorithm is able to identify this case and produces a schedule that guarantees maximum throughput, if packets share a common deadline. Furthermore, based on the optimal offline algorithms, an efficient online algorithm is designed which has been shown by simulations to produce near optimal results.

Deadline guaranteed packet scheduling for switches is a fundamental issue for providing guaranteed QoS in digital networks. It is a historically difficult NP-hard problem if three or more deadlines are involved. All existing algorithms have too low throughput to be used in practice. A key reason is they use packet deadlines as default priorities to decide which packets to drop whenever conflicts occur. Although such a priority structure can ease the scheduling by focusing on one deadline at a time, it hurts the throughput greatly. Since deadlines do not necessarily represent the actual importance of packets, we can greatly improve the throughput if deadline induced priority is not enforced. This paper first presents an algorithm that guarantees the maximum throughput for the case where only two different deadlines are allowed. Then, an algorithm called iterative scheduling with no priority (ISNOP) is proposed forthe general case where k > 2 different deadlines may occur. Not only does this algorithm have dramatically better average performance than all existing algorithms, but also guarantees approximation ratio of 2. ISNOP would provide a good practical solution for the historically difficult packet scheduling problem.

Due to the limited number of orthogonal channels in a multi-radio multi-channel wireless mesh network (MR-WMN), overlapping channel assignment (CA) is one of the main factors that greatly affect the network capacity. In this paper, we first propose a model for measuring achieved network capacity in MR-WMNs. Then we prove that finding an optimal overlapping CA in a given MR-WMN with odd number of channels, is equivalent to finding an optimal assignment by only using its orthogonal channels. This theory allows us to use fewer channels to solve complicated CA problems. Third, we prove that in 802.11b/g-based MR-WMN, the simplified optimization problem is a Max-3-Cut problem. Although this problem is NP-hard, it has an efficient approximation algorithm that achieves approximation ratio of 1.19616 probabilistically by using the algorithm for Max-Cut whose approximation ratio is 1.1383 probabilistically. Based on the algorithm for Max-Cut, this paper proposes Max-Cut-based channel assignment (MCCA) which uses a heuristic method to adjust the result produced by the Max-Cut algorithm to achieve an even better result. Finally, we perform extensive simulations to compare the MCCA with a state-of-the-art Tabu-Search based algorithm. The results show that the Max-Cut-based overlapping CA algorithm effectively improves on the network capacity.

Packet scheduling in switches plays an important role in providing guaranteed service to meet Quality-of-Service (QoS) requirements. In this paper, we revisit a historical Maximum Traffic Time-slot Scheduling (MTTS) problem for both circuit- and packet-switched traffic in SS/TDMA satellite systems proposed two decades ago by Bonuccelli et al.. They developed a two-step approach to solve the MTTS problem, which scheduled the circuit-switched traffic first into TDMA frames and then inserted packets from packet-switched traffic into empty slots in these scheduled TDMA frames as many as possible. This problem was referred as Incremental Time-slot Assignment (ITSA) Problem in their paper, and was proved to be NP-hard. Therefore, MTTS problem seems to be NP-hard due the the NP-hardness of ITSA problem induced by their two-step approach. However, in this paper, we show that MTTS problem is NOT NP-hard, since there exists an optimal algorithm for this problem. By aggregating the traffic in scheduled TDMA frames, an optimal algorithm based on network flow method is developed for MTTS problem, which can solve the MTTS problem in polynomial time. Theoretic proof for the optimality of our algorithm is given and simulations results further validate the correctness of our algorithm.

The rapid growth in micro-electronics technology and research in wireless sensor networks (WSNs) has made it possible to realize multimedia delivery on wireless multimedia sensor networks (WMSNs), consisting of tiny sensing devices. The volume and characteristics of multimedia data produced by WMSNs is quite different from the scalar data generated by conventional WSNs. This has raised the need to explore efficient routing protocols for multimedia data delivery in WMSNs, particularly supporting stringent quality of service (QoS). In this paper, we propose a novel cross-layer framework for QoS support in WMSNs, which optimizes the functionalities of communication protocols to maximize the number of video stream requests to be delivered while the imposed distortion constraint on the streams are met. QoS requirements are mapped on joint operations of application, network, MAC and link layers of the underlying communication framework. The experimental results demonstrate that the proposed framework achieves its objective efficiently.

Most packet scheduling algorithms for input-queued switches operate on fixed-sized packets known as cells. In reality, communication traffic in many systems such as Internet runs on variable-sized packets. Motivated by potential savings of segmentation and reassembly, there has been increasing interest in scheduling variable-sized packets in a nonpreemptive manner known as packet-mode scheduling. This paper studies frame-based packet-mode scheduling for better scalability. It first shows that the admissible condition is no longer sufficient for packet-mode scheduling. Then, a relation between the frame size and packet sizes is derived that classifies under what conditions the packet-mode scheduling problem is polynomial solvable or is NP-hard. This relation reveals an interesting result that under various packet size distributions, it may be polynomial solvable even if many different packet sizes occur in the packet set, whereas it may be NP-hard with just two packet sizes present. Finally, as a practical solution, this paper studies how a speedup can help packet-mode scheduling. It is shown that the admissible condition becomes sufficient also when a speedup of two is used. A simple algorithm with a speedup of two is presented.

We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. In this paper, we first present an efficient algorithm for the problem which runs in time O(k/sup 2/n+km+kn log(kn)), where n and m are the number of nodes and links in the network, and k is the number of wavelengths. We then analyze that the proposed algorithm requires O(d/sup 2/nk/sub 0//sup 2/+mk/sub 0/ log n) time for a restricted version of the problem in which the number of available wavelengths for each link is bounded by k/sub 0/ and k/sub 0/=o(n), where d is the maximum in-degree or out-degree of the network. It is surprising to have found that the time complexity for this case is independent of k. It must be mentioned that our algorithm can be implemented efficiently in the distributed computing environment. The distributed version requires O(kn) time and O(km) messages. Compared with a previous O(k/sup 2/n+kn/sup 2/) time algorithm, our algorithm has the following advantages. (1) We take into account the physical topology of the network which makes our algorithm outperform the previous algorithm. In particular, when k is small [e.g., k=O(log n)] and m=O(n), our algorithm runs in time O(n log/sup 2/ n), while the previous algorithm runs in time O(n log n). (2) Since our algorithm has high locality, it can be implemented on the network distributively.

We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. We first present fast, efficient algorithms both for the general problem and for a natural restricted version. The new algorithms outperform earlier work, providing time improvements amounting to an almost linear time factor in most cases. Also, all our algorithms can be implemented on the network in a distributed way.

A combined (2 log N-1)-stage interconnection network (denoted by /spl Delta//spl oplus//spl Delta/') is constructed by concatenating two Omega-equivalent networks (/spl Delta/ and /spl Delta/') with the rightmost stage of /spl Delta/ and the leftmost stage of /spl Delta/' overlapped. Benes network and the (2 log N-1)-stage shuffle-exchange network are two examples of such networks. Although these two networks have received intensive studies, the research on the topology of entire class of /spl Delta//spl oplus//spl Delta/' networks is very limited so far. In this paper, we study the topological structure of /spl Delta//spl oplus//spl Delta/' networks and propose an algorithm for determining topological equivalence between two given /spl Delta//spl oplus//spl Delta/' networks. We also present a simplified /spl Omega/-equivalence checking algorithm as a supporting result.

Mesh is one of the most commonly used interconnection networks and, therefore, embedding between different meshes becomes a basic embedding problem. Not only does an efficient embedding between meshes allow one mesh-connected computing system to efficiently simulate another, but it also provides a useful tool for solving other embedding problems. The authors study how to embed an s/sub 1//spl times/t/sub 1/ mesh into an s/sub 2//spl times/t/sub 2/ mesh, where s/sub i//spl les/t/sub i/ (i=1, 2), s/sub 1//spl les/t/sub 1/=s/sub 2/t/sub 2/, such that the minimum dilation and congestion can be achieved. First, they present a lower bound on the dilations and congestions of such embeddings for different cases. Then, they propose an embedding with dilation [s/sub 1//s/sub 2/]+2 and congestion [s/sub 1//s/sub 2/]+4 for the case s/sub 2//spl ges/s/sub 2/, both of which almost match the lower bound [s/sub 1//s/sub 2/]. Finally, for the case s/sub 1/

It is difficult to partition an arbitrary permutation into a minimum number of groups such that conflict-free paths for all source-destination pairs in each group can be established on an omega network. Based on linear algebra theory, this paper presents an optimal algorithm which solves this problem for the LC class of permutations on a large class of multi-stage networks. This algorithm extends the previous result which deals with the BPC class of permutations on the omega network.