Computer algorithms

In this project we perform data transmission across noisy channels and recover the message first by using the Golay code, and then by using the first-order Reed- Muller code. The main objective of this thesis is to determine which code among the above two is more efficient for text message transmission by applying the two codes to exactly the same data with the same channel error bit probabilities. We use the comparison of the error-correcting capability and the practical speed of the Golay code and the first-order Reed-Muller code to meet our goal.

Implementing Shamir's secret sharing scheme using floating point arithmetic would provide a faster and more efficient secret sharing scheme due to the speed in which GPUs perform floating point arithmetic. However, with the loss of a finite field, properties of a perfect secret sharing scheme are not immediately attainable. The goal is to analyze the plausibility of Shamir's secret sharing scheme using floating point arithmetic achieving the properties of a perfect secret sharing scheme and propose improvements to attain these properties. Experiments indicate that property 2 of a perfect secret sharing scheme, "Any k-1 or fewer participants obtain no information regarding the shared secret", is compromised when Shamir's secret sharing scheme is implemented with floating point arithmetic. These experimental results also provide information regarding possible solutions and adjustments. One of which being, selecting randomly generated points from a smaller interval in one of the proposed schemes of this thesis. Further experimental results indicate improvement using the scheme outlined. Possible attacks are run to test the desirable properties of the different schemes and reinforce the improvements observed in prior experiments.

In recent years, there has been an exponential increase in container volume shipment within intermodal transportation systems. Container terminals as part of the global port system represent important hubs within this intermodal transportation system. Thus, the need to improve the operational efficiency is the most important issue for container terminals from an economic standpoint. Moreover, intermodal transportation systems, ports and inland transport facilities should all be integrated into one coordinated plan. More specifically, a method to schedule different types of handling equipment in an integrated way within a container terminal is a popular topic for researchers. However, not many researchers have addresses this topic in relationship to the simulation aspect which will test feasible solutions under real container terminal environment parameters. In order to increase the efficiency of operations, the development of mathematical models and algorithms is critical in finding the best feasible solution. The objective of this study is to evaluate the feasible solution to find the proper number of Yard Trailers (YTs) with the minimal cost for the container terminals. This study uses the Dynamic YTs operation's method as a background for modeling. A mathematical model with various constraints related to the integrated operations among the different types of handling equipment is formulated. This model takes into consideration both serving time of quay cranes and yard cranes, and cost reduction strategies by decreasing use of YTs with the specific objective of minimum total cost including utilization of YTs and vessel berthing. In addition, a heuristic algorithm combined with Monte Carlo Method and Brute-Force Search are employed. The early Stage Technique of Monte Carlo method is proposed to generate vast random numbers to replicate simulation for real cases.

Delay tolerant networks (DTNs) are occasionally-connected networks that may suffer from frequent partitions. DTNs provide service despite long end to end delays or infrequent connectivity. One fundamental problem in DTNs is routing messages from their source to their destination. DTNs differ from the Internet in that disconnections are the norm instead of the exception. Representative DTNs include sensor-based networks using scheduled intermittent connectivity, terrestrial wireless networks that cannot ordinarily maintain end-to-end connectivity, satellite networks with moderate delays and periodic connectivity, underwater acoustic networks with moderate delays and frequent interruptions due to environmental factors, and vehicular networks with cyclic but nondeterministic connectivity. The focus of this dissertation is on routing protocols that send messages in DTNs. When no connected path exists between the source and the destination of the message, other nodes may relay the message to the destination. This dissertation covers routing protocols in DTNs with both deterministic and non-deterministic mobility respectively. In DTNs with deterministic and cyclic mobility, we proposed the first routing protocol that is both scalable and delivery guaranteed. In DTNs with non-deterministic mobility, numerous heuristic protocols are proposed to improve the routing performance. However, none of those can provide a theoretical optimization on a particular performance measurement. In this dissertation, two routing protocols for non-deterministic DTNs are proposed, which minimizes delay and maximizes delivery rate on different scenarios respectively. First, in DTNs with non-deterministic and cyclic mobility, an optimal single-copy forwarding protocol which minimizes delay is proposed.

Sensors are used to monitor and control the physical environment. A Wireless Sen- sor Network (WSN) is composed of a large number of sensor nodes that are densely deployed either inside the phenomenon or very close to it [18][5]. Sensor nodes measure various parameters of the environment and transmit data collected to one or more sinks, using hop-by-hop communication. Once a sink receives sensed data, it processes and forwards it to the users. Sensors are usually battery powered and it is hard to recharge them. It will take a limited time before they deplete their energy and become unfunctional. Optimizing energy consumption to prolong network lifetime is an important issue in wireless sensor networks. In mobile sensor networks, sensors can self-propel via springs [14], wheels [20], or they can be attached to transporters, such as robots [20] and vehicles [36]. In static sensor networks with uniform deployment (uniform density), sensors closest to the sink will die first, which will cause uneven energy consumption and limitation of network life- time. In the dissertation, the nonuniform density is studied and analyzed so that the energy consumption within the monitored area is balanced and the network lifetime is prolonged. Several mechanisms are proposed to relocate the sensors after the initial deployment to achieve the desired density while minimizing the total moving cost. Using mobile relays for data gathering is another energy efficient approach. Mobile sensors can be used as ferries, which carry data to the sink for static sensors so that expensive multi-hop communication and long distance communication are reduced. In this thesis, we propose a mobile relay based routing protocol that considers both energy efficiency and data delivery delay. It can be applied to both event-based reporting and periodical report applications.