In this paper, we investigate the tags polling problem for large, multireader RFID systems. We take an approach completely different from that used so far for multireader protocols. Up to now, in the proposed protocols for this and related problems, first readers are scheduled so that those with overlapping ranges never operate at the same time. Then, proper protocols for each so scheduled reader are applied. Here, we schedule the tags instead of the readers so that tags whose transmission can be received by a common reader, never operate at the same time. Then, we present a polling protocol that takes advantage of this paradigmatic shift. The performance improvement of our protocol over the known ones is very large, going from two times to seven times, as shown by a simulation experiment we set up, and whose results are also presented.

In this paper, we examine the problem of packet scheduling in a single-hop multichannel system, with the goal of minimizing the average message waiting time. Such an objective function represents the delay incurred by the users before receiving the desired data. We show that the problem of finding a schedule with minimum message waiting time is NP-complete, by means of polynomial time reduction of the time table design problem to our problem. We present also several heuristics that result in outcomes very close to the optimal ones. We compare these heuristics by means of extensive simulations.

We consider a cognitive radio scenario where the communication between two secondary users (SUs) exploits opportunistic spectrum access (OSA) over a wireless channel licensed to primary users (PUs). Assuming a slotted MAC over a single frequency channel and imperfect spectrum sensing, we address the problem of determining the packet size and Forward Error Correction (FEC) coding rate that maximize the SU communication goodput, i.e., the amount of payload bits correctly received in the unit time. Assuming a Markovian model for the PU activity, a saturation regime for the SU, and periodic channel sensing, we find out the mean time between two consecutive packet transmissions and derive approximate analytical expressions, in closed form, which provide upper and lower bounds on the SUs goodput. Such expressions show the dependence of the SU goodput on packet size, FEC coding rate, signal to noise plus interference ratio, amount of resources allocated to sensing, packet overhead, and primary traffic statistics. We provide simulation results showing that the derived analytical expressions are very close to the actual system performance. We also evaluate the sensitivity of the optimal packet size and FEC coding rate pair to the operational conditions represented by the received power and the PU traffic load, showing that the optimal pair is very sensitive to the former, and only moderately affected by the latter.

Radio Frequency IDentification (RFID) systems are becoming more and more popular in the field of ubiquitous computing, in particular for objects identification. An RFID system is composed by one or more readers and a number of tags. One of the main issues in an RFID network is the fast and reliable identification of all tags in the reader range. The reader issues some queries, and tags properly answer. Then, the reader must identify the tags from such answers. This is crucial for most applications. Since the transmission medium is shared, the typical problem to be faced is a MAC-like one, i.e. to avoid or limit the number of tags transmission collisions. We propose a protocol which, under some assumptions about transmission techniques, achieves a 60% performance on the average (in terms of transmitted bits). It is based on a proper recursive splitting of the concurrent tags sets and on signal storing and later cancellation, until all tags have been identified.

In this paper, we investigate a scheduling problem in systems adopting OFDMA transmission technique at the physical layer, like WiMAX (IEEE 802.16) systems. In such systems, carriers with different rates must be assigned to users, each carrier being assigned to one user at most, each user can be scheduled on multiple carriers. The objective of our problem is to produce a legal schedule (i.e. one meeting all the system constraints) with minimum length. We first show that the above problem is NP-complete, and thus computationally intractable, even in an extremely simple case. Then, we propose several very simple and fast suboptimal heuristics, and evaluate their average performance by means of simulation experiments. Some of the proposed heuristics perform very well, being in most cases within 10% of the optimal (minimal) schedule length.

In this paper, we approach the problem of identifying a set of objects in an RFID network. We propose a modified version of slotted aloha protocol to reduce the number of transmission collisions. All tags select a slot to transmit their ID by generating a random number. If there is a collision in a slot, the reader broadcasts the next identification request only to tags which collided in that slot. Simulation results show that our approach performs better than framed slotted aloha and query tree based protocols, in terms of number of slots needed to identify all tags, which is a commonly used metric, strictly related to delay

Third generation mobile communication systems will provide more advanced types of interactive and distribution services, and video is one of the most prominent applications for multimedia communications. Adapting the media content to different networks characteristics (communication links and access terminals), in order to enable video delivery with acceptable service quality, is one of the most important problems in this setting. In this paper, we consider one of the video adaptation methods, namely video transcoding, and we present new buffer-based strategies for temporal video transcoding in a real-time context. Simulation results show that our strategies achieve a good performance in hard transcoding conditions also.

LEO/MEO constellations of communication satellites have recently been proposed as a powerful tool for improving internet performance and for extending it beyond the earth (InterPlanetary Internet). Several aspects of such usage must still be investigated. Among them, proper routing and MAC protocols play a prominent role. In this paper,we assume that the MAC protocol is an MF/TDMA one (as usual in satellite communication), and we consider the problem of assigning packets to a set of shortest paths in a satellite constellation, with the goal of minimizing the overall packet scheduling problem. We present an optimal polynomial time algorithm which works offline and balances the load over all possible shortest paths, allowing a minimum schedule length for the entire constellation to be found in polynomial time.

We consider broadcast-and-select networks based on optical passive stars. In these single-hop networks, communicating pairs can exchange messages directly, without the need to store information at intermediate nodes for later forwarding. Messages are transmitted in a packetized way, and each message has an associated deadline. In order to guarantee the message reception timeliness, we ask that all the messages are received within their corresponding deadline. We show that this scheduling problem is strong NP-complete, even in a very restricted case. Then, we turn our attention to fast approximating heuristics. We present four of them, assess their average performance by means of computer simulation, and give their worst-case performance bounds. Such bounds can be effectively used to test the success of the schedule before generating it.

In this paper, we study the problem of on demand minimum length packet scheduling in single-hop multichannel systems. Examples of these systems are those centered around switching networks, like crossbar switches, and WDM optical fiber networks. On demand scheduling require that packets are scheduled upon receipt, and without changing the schedule of earlier packets. On demand scheduling is performed by on-line algorithms. In this paper we-show that a large group of online scheduling algorithms, called maximal algorithms, are asymptotically optimal (in the worst case sense). This result is established by first giving the competitive ratio of these algorithms (nearly 3), and then by showing that no on-line algorithm can (asymptotically) perform better in the worst case. Then, we run a simulation experiment on randomly generated problem instances, whose outcome indicates an average increase of the schedule length of maximal algorithms, of 5% with respect to the lower bound.

Switching networks are the core of many communication and multiprocessor systems. In these systems, a set of entities (communication equipment or processors) communicate through the switching network by exchanging messages. Simultaneous transmission or reception of two 01 more different messages through an input or output port results in the corruption of the messages (also called collision), which are useless and must be retransmitted later. This causes a performance degradation. Collisions can be avoided only by a proper scheduling of the messages. The same problem also arises in single-hop purely optical WDM systems, where simultaneous reception or transmission over the same wavelength channel results in a collision. In this paper, we study the problem of minimum length scheduling of a set of messages subject to precedence constraints. We show that the decision version of the problem is NP-complete even in very restricted cases. This means that the optimization problem cannot be solved in polynomial time, unless P=NP. Since the problem cannot be optimally solved by fast algorithms, we then investigate the existence of polynomial time approximation algorithms, by first proving that approximation algorithms cannot exist with performance ratio bounded by 4/3 or smaller and successively presenting an /spl epsiv/-approximation algorithm with /spl epsiv/<2 for the case of two precedence classes of messages. Finally, we assess the existence of an asymptotically optimal schedule in the general case of an unrestricted number of precedence classes.

Hidden terminal interference is caused by the (quasi-) simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station. This interference lowers the system throughput and increases the average packet delay. Some random access protocols that reduce this interference have been proposed, e.g., BTMA protocol. However, the hidden terminal interference can be totally avoided only by means of code division multiple access (CDMA) schemes. In the paper, the authors investigate the problem of assigning orthogonal codes to stations so as to eliminate the hidden terminal interference. Since the codes share the fixed channel capacity allocated to the network in the design stage, their number must not exceed a given bound. The authors seek assignments that minimize the number of codes used. They show that this problem is NP-complete, and thus computationally intractable, even for very restricted but very realistic network topologies. Then, they present optimal algorithms for further restricted topologies, as well as fast suboptimal centralized and distributed heuristic algorithms. The results of extensive simulation set up to derive the average performance of the proposed heuristics on realistic network topologies are presented.>

Considers the optimal (i.e., minimum length) time slot assignment problem for variable bandwidth switching systems. Existing algorithms for this problem are known to be pseudo-polynomial. The practical question of finding a fast optimal algorithm, as well as the theoretical question of whether the above problem is NP-complete were left open. The authors present a technique to show polynomial time complexity of some time slot assignment algorithms. Such a technique applies to an algorithm proposed by Chalasani and Varma in 1991 (called the CV algorithm), as well as to a network flow based optimal algorithm, proposed in the present paper for the first time. The CV algorithm and the one proposed are slightly different. Thus, the authors give an answer to both the above questions, by establishing that the problem is in P, and by showing effective algorithms for it.>

Hidden terminal interference is caused by the simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station. The authors investigate the problem of assigning orthogonal codes to stations to eliminate the hidden terminal interference and minimize the number of codes used. It is shown that this problem is computationally intractable, even for very restricted but very realistic network topologies. Optimal algorithms for code assignment in special networks, as well as both centralized and distributed suboptimal heuristic algorithms for general topologies, are presented. The results of extensive simulations to derive the average performance of the proposed heuristics on realistic network topologies are presented.>

The problem of minimizing the internetwork packet fragmentation cost by selecting an appropriate route from the origin to the destination network is investigated. It is shown that this problem is NP-complete, and optimal (minimum fragmentation cost) paths cannot be computed by fast algorithms when the intranetwork strategy is used. Then, the internetwork fragmentation strategy is considered, and a fast (i.e., polynomial time) routing algorithm, called Maxbottleneck, is presented. When a greedy fragmentation scheme is adopted, like the classical maximal one, the algorithm produces an optimal path when some conditions on the networks' maximum packet sizes are met. A novel, non-greedy fragmentation scheme called bottleneck is also proposed. It is shown that the path produced by Maxbottleneck is always optimal when the bottleneck scheme is used.>

The Satellite-Switched Time-Division Multiple Access (SS /TDMA) is a technique effectively used in wideband communication satellites. A very important problem for SS/TDMA systems is the proper communications scheduling over the satellite equipment. This problem is equivalent to decomposing a given traffic matrix T into a positive linear combination of $( 0,1 )$-matrices satisfying additional technology-dependant constraints. The sum of the multiplying constants represents the time taken by the satellite to handle the communications and must be minimum in order to achieve an efficient use of the equipment. A polynomial time optimal algorithm for the SS/TDMA scheduling problem for systems with variable bandwidth beams and restricted multiplexing and demultiplexing is presented. As a corollary of the presented results, another generalization of the classical Birkhoff-von Neumann Theorem is established.

The heterogeneous traffic in this environment can be categorized into a rapidly changing type composed of packet switched data traffic and a relatively static type composed of circuit switched voice traffic. From the time-slot assignment viewpoint, the problem is to construct an efficient TDMA frame that permits the static voice traffic to be transmitted and, then, on a frame-by-frame basis to attempt to insert the data packets into the slots that are unused by the voice traffic. It is proved that the problem is NP-complete, even for very simple traffic configurations. Several suboptimal fast heuristic algorithms are presented and empirically compared by experiments on randomly generated traffic patterns. The experiments reveal that, on the average, the algorithms give close to the optimal performance.>

The use of a fault-tolerant VLSI system for storing and solving linear programming problems is presented. The system can bear multiple faults in processing elements and/or links and still function with an acceptable performance degradation. It is based on an interconnection pattern consisting of a complete binary tree in which spare links between cousin nodes are added so as to reconfigure it as a ternary tree. At any given time of a computation, faulty processing elements and/or links are circumvented by using such spare links. It is shown that the total silicon area required by this structure is only a constant factor higher than that of a complete binary tree. The result is used to give an efficient implementation of the simplex algorithm in which the time required to perform a single pivot step matches a previously established lower bound for tree machines in spite of faults.>

A fast (polynomial time) network-flow-based algorithm is presented for time slot assignment in time-division-multiplexing (TDM) hierarchical switching systems. For a nonblocking time-multiplexed central switch the algorithm produces a conflict-free time slot assignment for a given frame (whenever this is possible) on O(M/sup 5/) time, where M is the system size.>

The use of a special-purpose VLSI chip for solving a linear programming problem is presented. The chip is structured as a mesh of trees and is designed to implement the well-known simplex algorithm. A high degree of parallelism is introduced in each pivot step, which can be carried out in O (log n) time using an m × n mesh of trees having an O(mn log m log3 n) area where m − 1 and n − 1 are the number of constraints and variables, respectively. Two variants of the simplex algorithm are also considered: the two-phase method and the revised one. The proposed chip is intended as being a possible basic block for a VLSI operations research machine.

In this paper we study the time slot assignment problem in clusters of SS/TDMA satellite systems interconnected through intersatellite links. We show that the problem of finding an assignment which minimizes the total transmission time is NP-complete, i.e., computationally intractable, even for quite restricted intersatellite link patterns and simplified system models. Successively, we focus our attention on clusters of two satellites, proposing a branch-and-bound optimal algorithm and two fast heuristic algorithms. We investigate the performance of the proposed heuristic algorithms both by a theoretical worst case bound and by simulation trials showing that the produced solutions are close to the optimal on the average.

The problem of sorting n elements using VLSI chips that can sort only q(q < n) elements at a time is considered. The proposed VLSI chip consists of a mesh of trees. Two classical algorithms, i.e., merge sort and bitonic sort, are modified to efficiently solve the external sorting problem using this chip.

A VLSI chip for performing relational data base operations is proposed. The chip is a tree of processors (TOP), where each chip has elementary storage and processing capabilities. A relation will be stored in the lowest levels of a TOP. More precisely, every m-tuple will occupy a subtree whose root is s= [log2(m+1)] =1 levels above the leaves. Denoting by h the height of the tree, the upper h-s levels will be used for routing and bookkeeping purposes. A number of basic operations such as allocate and deallocate subtrees, insert and compare m-tuples etc., are defined for the TOP's. Relational operations are effectively performed as simple combinations of basic operations. The architecture of a data base machine based on TOP's is also sketched. Such a machine is feasible with the current VLSI technology and could become attractive in few years if density and performance of VLSI keep improving at the current rate.

In this paper we study the traffic scheduling problem in an SS/TDMA system with interfering beams. We investigate a twostep approach, the first step being the assignment of orthogonal polarization to reduce the interference, and the second step being the scheduling of traffic, taking into account the "resultant" interference. The first step we show can be solved in polynomial time in most cases, while the second step we prove to be NP-complete, even for very simple interference patterns. We suggest several suboptimal algorithms for this second step and, by experimental trials on randomly generated traffic patterns, show that on the average they produce close to optimal solutions.

In this paper we consider an SS/TDMA system withMuplink beams andNdownlink beams, where uplink beamihas bandwidth βiand downlink beamjhas bandwidth αj. The maximum traffic which can be handled by the satellite (in any given time slot) is assumed to beK. Multiplexing and demuitiplexing are also assumed. An optimal time slot assignment algorithm to minimize the total transmission time for any given traffic demand matrix is proposed and analyzed. Other system configurations of interest are also discussed.