With the progress of wireless radio technology and telecommunication, various wireless specifications and protocols form the unhandy heterogeneous network. The routing problems in heterogeneous network become popular researches nowadays. In this thesis, we integrate cellular (3G) network and Mobile Ad-Hoc Network (MANET) into a hybrid network. This hybrid network is called heterogeneous wireless network(HWN) with multi-cells architecture to overcome the weakness of cellular network and Ad-Hoc network. Based on HWN, we propose a routing algorithm with quality of service (QoS) supported for requirements in the original homogeneous cellular network and Ad-Hoc network. Simulation results show that HWN with the proposed algorithm has lower request block rate and shorter transmission time.

An ad-hoc network operates without a central entity or infrastructure, and is composed of highly mobile hosts. In ad-hoc network, routing protocols are with host mobility and bandwidth constraints. There have been many recent proposals of routing protocols for ad-hoc networks. A recent trend in ad hoc network routing is the reactive on-demand philosophy where routes are established only when required. AODV(Ad-hoc On-demand Distance Vector routing) evaluates routes only on an as-needed basis and routes are maintained only as long as they are necessary. Because the network topology changes frequently in ad-hoc networks, some on-demand protocols with multi-paths or backup routes have been proposed. Sung-Ju Lee and Mario Gerla proposed an AODV-BR scheme to improve existing on-demand routing protocols by creating a mesh and providing multiple alternate routes . The algorithm establishes the mesh and multi-path using the RREP (Route Reply) of AODV, which does not transmit any extra control message. In this paper, we propose two schemes : AODV-ABR(Adaptive Backup Route) and AODV-ABL (Adaptive Backup Route and Local repair) to increase the adaptation of routing protocol to topology changes by modifying AODV-BR. In AODV-ABR, the alternative route can be creating by overhearing not only RREP packets but also data packets. AODV-ABL combines the benefits of AODV-ABR and Local Repair. Finally, we evaluate the performance improvement by simulation.

With recent growth in mobile components and advances in wireless communication technology, mobile computing is an increasingly important area of research. Enabling mobility in IP networks becomes more and more significant. Mobile IP is the only current means for offering seamless roaming to mobile computers in the Internet. It has recently progressed along the ladder to standardization within the Internet Engineering Task Force (IETF). However, Mobile IP suffers from so-called triangular-routing problem and packet loss due to handoff. In this paper, we propose a new architecture to solve these two problems noted above. We assume that network routers such as Home Agent¡BForeign Agent¡BGeneral Router can equip our Pre-Accessing Engine (Mobile IP Engine) to access IP packets before IP routing Engine. With our Mobile IP table established in Mobile IP Engine, we can set up a transmission path for each correspondent node (CN) to transmit data to mobile node (MN). Therefore, we not only solve triangular-routing problem by direct transmission path, but also decrease handoff latency from path updating function. Furthermore, we use retransmission and flush schemes to avoid packet loss and out-of-order problems. Finally, we use simulation to prove our architecture is useful.

We propose a novel multicast routing protocol, called adaptive multicast routing protocol for MANETs (Mobile ad hoc routing protocol). Multicast routing protocols can be classified two types according the structure used to establish route. Existing protocols are either tree-based or mesh-based. In mesh-based routing protocols, a reliable protocol ODMRP was proposed. In ODMRP, each sender has to broadcast control packet periodically in order to build mesh. But with an increase of number of senders, control overhead causes reliability reduced because of a large amount of overhead and collisions. Hence, ODMRP is not work well in this case. We proposed our scheme to aim at the drawback of ODMRP. We use packet delivery ratio (PDR) to determine if the load of network is congestion. When packet delivery ratio is high, it means that the network traffic load is low, and vice versa. We determine whether a sender broadcasts Join-Query control packet or not according to packet delivery ratio. As packet delivery ratio is decrease, a sender does not broadcast Join-Query as far as it can in order to avoid collisions. However the packet delivery ratio is increase, senders have strong probability to broadcast Join-Query to establish mesh nodes. We can improve reliability and reduce overhead is caused by control packets with this way.

Wireless Sensor Network (WSN) has become a popular wireless technology in recent years. In WSN, a large number of sensors are used to collect data and forward data hop-by-hop to a sink. Due to the unbalancing of traffic load, some grid nodes may consume more energy and their packet loss ratio may be increased as well. In order to improve above-mentioned shortcomings, in this Thesis, we propose an Adaptive Grid-based Data Collection (AGDC) scheme. Because a mobile sink may move, it is possible the traffic load of primary grid nodes can be changed in WSN. According to the distribution of traffic load, the AGDC can adjust transmission range to allocate one or more temporary grid nodes between two primary grid nodes. Through the added temporary grid nodes, traffic load is evenly dispersed among different grid nodes. We allow the primary grid nodes to use smaller transmission power to save energy and allow the temporary grid nodes to buffer data to reduce packet loss ratio. For the purpose of evaluation, we perform simulation on NS-2. With the proposed AGDC scheme, the transmission range of a primary grid node can be set to an appropriate distance to reduce power consumption and packet loss ratio. Since the packet loss ratio is reduced, the throughput of entire WSN is increased.

In this study we consider an inventory routing problem in which a supplier distributes a single product to multiple retailers in a finite planning horizon. Retailers should satisfy the deterministic and dynamic demands of end customers in the planning horizon, but the retailers can backorder the demands of end customers considering the supply chain costs. In each period the supplier decides the retailers to be visited, and the amount of products to be supplied to each retailer by a fleet of vehicles. The decision problems of the supplier are about when, to whom and how much to deliver products, and in which order to visit retailers while minimizing system-wide costs. We propose a mixed integer programming model and a Lagrangian relaxation based solution approach in which both upper and lower bounds are computed. We test our solution approach with test instances taken from the literature and provide our computational results.

Reliable communication in the hypercube with the safety vectors is discussed in this thesis. In the hypercube, the safety levels and the safety vectors, used to guide fault-tolerant routing, is a kind of limited global information based methods. The transmission cost of the safety vectors is O(n2) for each node. For increasing the probability of optimal routing, we attempt to increase the transmission cost for obtaining more information. We propose two methods with O(n3) transmission cost in each node, the enhanced safety vector and the spanning safety vector, to achieve the goal. We also propose the probabilistic safety vector which provides the probability of optimal routing for each node. Finally, our experiments show that the routing with the enhanced safety vector is more reliable than the safety vectors and the extended safety vectors, which were propose the probabilistic safety vector.

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that network contain only one faulty element. In order to ensure the message can be arrived. We present a fault-tolerant message routing algorithm which being the secondary path, as the optimal path can't be connected in the double-loop networks.

As fabrication technology keeps advancing, many deep submicron (DSM) effects have become increasingly evident and can no longer be ignored in Very Large Scale Integration (VLSI) design. In this dissertation, we study several deep submicron problems (eg. coupling capacitance, antenna effect and delay variation) and propose optimization techniques to mitigate these DSM effects in the place-and-route stage of VLSI physical design. The place-and-route stage of physical design can be further divided into several steps: (1) Placement, (2) Global routing, (3) Layer assignment, (4) Track assignment, and (5) Detailed routing. Among them, layer/track assignment assigns major trunks of wire segments to specific layers/tracks in order to guide the underlying detailed router. In this dissertation, we have proposed techniques to handle coupling capacitance at the layer/track assignment stage, antenna effect at the layer assignment, and delay variation at the ECO (Engineering Change Order) placement stage, respectively. More specifically, at layer assignment, we have proposed an improved probabilistic model to quickly estimate the amount of coupling capacitance for timing optimization. Antenna effects are also handled at layer assignment through a linear-time tree partitioning algorithm. At the track assignment stage, timing is further optimized using a graph based technique. In addition, we have proposed a novel gate splitting methodology to reduce delay variation in the ECO placement considering spatial correlations. Experimental results on benchmark circuits showed the effectiveness of our approaches.

Mobile ad hoc network is an architecture which do not exist any infrastructure or centralized administration. There are many routing protocols have been proposed so far, such as AODV, DSR and CGSR. These protocols were classified as reactive in which routes are established only when required. Due to the movement of mobile nodes, network topology changes frequently, and the routing path could be broken easily. This phenomenon will cause higher routing overhead and delivery latency. In conventional routing protocols, the source-destination pair only establishes a single path for data transmission. These routing scheme, however, suffer from the drawback of node movement. When route broken, the source node must reconstruct another new path. This paper presents an adaptive routing protocol named Adaptive Route Selection Scheme of Multiple Paths for Mobile Ad Hoc Network (ARSMA). The aim of the work is to improve the delivery ratio. In the route request phase, source nodes will discovery two routes to the destination node, one for primary path, and the other for the backup path. During the discovery procedure, each node will estimate the link expire time through the movement speed and direction of the precursor node. When a link breakage is about to occur, source node will try to switch the transmission to the backup route.The simulation result shows that ARSMA is able to achieve a remarkable improvement in delivery ratio and end-to-end dealy.