Search

In this paper, a new mathematical programming formulation is developed for minimizing the schedule length in multihop wireless networks based on the optimal joint scheduling of transmissions across multi-access communication links and the allocation of transmit power levels while meeting the requirements on the signal-to-interference-plus-noise ratio at intended receivers. The authors prove that the problem can be represented as a mixed-integer linear programming (MILP) and show that the latter yields a solution that consists of transmit power levels that are 'strongly Pareto optimal.' It was demonstrated that the MILP formulation can be used effectively to derive optimal scheduling and power levels for networks with as many as 30 designated communication links. The authors show that the MILP formulation can also be effectively solved to provide upper and lower bounds (corresponding to an approximation factor [DELTA]) for the optimum schedule length of networks with as many as 100 designated links. It is proved that the integrated link scheduling and power control problem (ILSP) is NP-complete. Consequently, a heuristic algorithm of polynomial complexity is developed and investigated for solving the problem in a timely and practical manner. The algorithm is based on the properties of a novel interference graph, i.e., the 'generalized power-based interference graph,' whose 'chromatic' and 'independence numbers' provide fundamental bounds for the ILSP. It is demonstrated that the frame length of schedules realized by the heuristic scheme resides in the 25th percentile of those attained by the optimal mechanism for randomly generated topologies with as many as 30 designated communication links. Furthermore, it is shown that the algorithm significantly outperforms a corresponding algorithm presented in the literature. Index Terms--Combinatorics, graph theory, mathematical programming/optimization, medium access control (MAC), multihop wireless networks, power control.

Aloha-type random-access protocols have been employed as access-control protocols in wireline and wireless, and stationary and mobile, multiple-access communications networks. They are frequently employed by the control and signaling subsystem of demand-assigned multiple-access protocols for regulating the sharing of a multiaccess communications channel. The correct design and sizing of the random-access operated control/signaling channel is a critical element in determining the performance of these networks. Excessive delays in the transport of signaling messages (induced by too many collisions and retransmissions) lead to unacceptable session-connection setup times. This is of particular concern when the message traffic is highly bursty, as it tends to be under a multitude of often-observed traffic-loading scenarios. Consequently, in this paper, we investigate the performance behavior of a random-access protocol when loaded by bursty traffic processes. The latter often exhibit long-range dependence (LRD). The LRD traffic flows are modeled here as multiplicative multifractal processes. The random-access protocol is modeled as an Aloha channel with blocking. We demonstrate that the burstiness feature of the traffic processes, rather than their LRD character, is the essential element determining the performance behavior of the protocol. When the loading-traffic process is not very bursty, we show that the performance of the random-access channel can be even better than that exhibited under Poisson traffic loading; otherwise, performance degradation is noted. We demonstrate the impact of the selection of the protocol-operational parameters in determining the effective performance behavior of the random-access protocol. Index Terms--Aloha, long-range dependence, multifractal traffic processes, multiple access, performance evaluation.

A multiaccess communications channel which is shared on an integrated circuited-switched and packet-switched basis is considered. Applications include time-division multiplexing and demand-assigned/TDMA communication channels which are shared by circuit-switched services (such as isochronous voice) and packet-switched services (such as data). Frames of fixed duration are established and divided into two parts: one part is used for voice transmissions while the other part serves to accommodate packetized data traffic. These two parts are separated by a movable boundary, so that data traffic can use the frame capacity which is temporarily unoccupied by voice transmissions. An exact expression is derived for the mean packet queue-size and delay. To reduce the computational complexity involved in using this expression, simpler expressions for upper and lower bounds are derived for the mean packet queue-size and packet delay. Examples demonstrating the tightness of these numerically efficient bounds are presented.

Under a TDMA (time-division multiple-access) scheme, a station shares a multiple-access communications channel by transmitting its messages during its dedicated time slots. In many networking (multiple-access, multiplexing, time-slot interchange switching, etc.) situations, each station is allocated a number of contiguous time slots during each time frame. In this paper, we present an exact result concerning the queue-size and message delay analysis of TDMA systems in which a station is allocated multiple consecutive slots per frame. We obtain the generating function of the system queue-size for a general independent arrival message process. Messages consist of a random number of packets, following a geometric distribution. We then derive an exact result for the generating function of the message delay for various common message arrival processes, as well as tight bounds for the mean message queue-size and delay. Our results are compared to previously derived approximations. We also prove that a slot allocation scheme which distributes station slots uniformly over the frame yields a message-delay lower bounds. Our results also apply to the analysis of time-shared reservation schemes.