||"Anytime, anywhere" communication, information access, and processing are much cherished in modern societies because of their abilities to bring flexibility, freedom, and increased efficiency to individuals and organizations. Wireless communications, by providing ubiquitous and tetherless network connectivity to mobile users, are therefore bound to play a major role in the advancement of our society. Although initial proposals and implementations of wireless communications are generally focused on near-term voice and electronic messaging applications, it is recognized that future wireless communications will have to evolve towards supporting a wider range of applications, including voice, video, data, images, and connections to wired networks. This implies that future wireless networks must provide packet-based transport and bandwidth-upon-demand as well as support multimedia applications, thereby introducing a new set of challenges. One major challenge being how to provide quality-of-service (QoS) guarantees to various multimedia applications in a wireless environment. Typical traffic in multimedia applications can be classified as either Constant- Bit-Rate (CBR) traffic or Variable-Bit-Rate (VBR) traffic. In particular, scheduling the transmission of VBR multimedia traffic streams in a wireless environment is very challenging and is still an open problem. In general, there are two ways to guarantee the QoS of VBR multimedia streams, either deterministically or statistically. The statistical models for characterizing bursty VBR traffic sources are either not powerful enough to capture the important burstiness and time correlation of realistic sources, or they are too complex for practical implementation for connection admission control (CAC) algorithms. The deterministic models are normally be more pessimistic. In particular, the throughput and the channel utilization of a deterministic bounded system are typically smaller than that of a statistical bounded system. However, the advantages of bounded models are that they can provide deterministic bounds such that no admitted connection would violate its QoS guarantees. Recently, CAC algorithms and medium access control (MAC) protocols have been proposed for wireless networks. Nearly all of the proposed algorithms only provide statistical, or soft, QoS Guarantees. That is, they can only provide probabilistic bounds on the percentage of packets delivered within the QoS constraints. Even if a connection is admitted to the network, the network cannot fully guarantee that no QoS of any connection is violated. That is, the required or the desired QoS of some connections may still be violated in some cases. In this thesis we consider deterministic quality-of-service guarantees. We propose a method for constructing a packet dropping mechanism that makes decisions as to when we need to drop packets while still not violating any QoS guarantees. This mechanism is based on a mathematical framework that determines how many packets can be dropped while the required QoS can still be preserved. This is achieved by employing: 1) An accurate traffic characterization of the VBR multimedia traffic steams; 2) A traffic regulator that can provide bounded packet loss; and 3) A traffic scheduler that can provide bounded packet delay. The combination of traffic c haracterization, regulation, and scheduling can provide bounded packet loss and packet delay deterministically. This is a distinction from traditional deterministic QoS schemes where a 0% packet loss is always assumed with deterministically bounding the packet delay. The uniqueness of our scheme is that it can provide bounded loss and bounded delay deterministically. We performed a set of performance evaluation experiments. The results will demonstrate that our proposed QoS guarantee schemes can significantly support more connections than a system which do not allow any loss at the same required QoS. Moreover, from our evaluation experiments, we found that the proposed algorithms are able to out-perform scheduling algorithms adopted in state-of-the-art wireless MAC protocols, e.g., MASCARA, when the worst-case traffic is being considered. We found that there are many fewer connections whose required QoS are violated using our proposed algorithm. As a result, the admitted connections are served with better hard QOS using our proposed scheme.