Computer algorithms

Quantum computers and quantum computing is a reality of the near feature. Companies
such as Google and IBM have already declared they have built a quantum computer
and tend to increase their size and capacity moving forward. Quantum computers have
the ability to be exponentially more powerful than classical computers today. With this
power modeling behavior of atoms or chemical reactions in unusual conditions, improving
weather forecasts and traffic conditions become possible. Also, their ability to exponentially
speed up some computations makes the security of todays data and items a major
concern and interest. In the area of cryptography, some encryption schemes (such as RSA)
are already deemed broken by the onset of quantum computing. Some encryption algorithms
have already been created to be quantum secure and still more are being created
each day. While these algorithms in use today are considered quantum-safe not much is
known of what a quantum attack would look like on these algorithms. Specifically, this
paper discusses how many quantum bits, quantum gates and even the depth of these gates
that would be needed for such an attack. The research below was completed to shed light
on these areas and offer some concrete numbers of such an attack.

Wireless ad hoc networks (or simply ad hoc networks) are infrastructureless multihop
networks consisting of mobile or stationary wireless devices, which include mobile
ad hoc networks (MANETs) and wireless sensor networks (WSNs). These networks are
characterized by limited bandwidth and energy resources, frequent topology changes,
and a lack of central control. These characteristics lead to the research challenges of ad
hoc networks. The algorithms designed for ad hoc networks should be localized, selforganizing,
and energy efficient. A connected dominating set (CDS) is frequently used in
ad hoc networks as a virtual backbone to support efficient routing, service discovery, and
area monitoring. In addition, efficient broadcasting (i.e., finding a small set of forward
nodes to ensure full delivery) can be viewed as forming a CDS on-the-fly. The periodically
maintained virtual backbone is called a static CDS, and the temporarily formed
forward node set is called a dynamk CDS. For efficiency and robustness, the ideal CDS
construction algorithm is lightweight, has fast convergence, and minimizes the CDS size. Recently, due to some specific applications and new techniques, the concept of a connected
dominating set can be modified or further extended for more efficient usage.
This dissertation focuses on the variations with applications of the connected dominating
set, designing new concepts, and developing new algorithms for them. A review
of CDS construction algorithms for ad hoc networks has been provided at the beginning.
An efficient scheme, called Rule K, has been proposed for static CDS construction. Rule
K achieves a probabilistic constant upper bound on the expected CDS size, which is currently
the best known performance guarantee for localized CDS algorithms. Several CDS
algorithms are extended to generate the extended CDS, which exploits the cooperative
communication technique to further reduce the size of CDS. A k-coverage set is developed
for higher robustness. With the equipment of directional antennas , the transmission
can be restricted to some certain directions to reduce interference and energy consumption.
The corresponding directional CDS is discussed. Finally, a wireless sensor and actor
network (WSAN) is introduced and localized algorithms are designed for it.

In recent years, many protocols for efficient Multicasting have been proposed.
However, many of the Internet Service Providers (ISPs) are reluctant to use multicastenabled
routers in their networks. To provide such incentives, new protocols are
needed to improve the quality of their services. The challenge is to find a compromise
between allocating Bandwidth (BW) among different flows in a fair manner, and
favoring multicast sessions over unicast sessions. In addition, the overall higher level
of receiver satisfaction should be achieved.
In this dissertation, we propose three new innovative protocols to favor
multicast sessions over unicast sessions. Multicast Favored BW Allocation-
Logarithmic (MFBA-Log) and Multicast Favored BW Allocation-Linear (MFBALin)
protocols allocate BW proportional to the number of down stream receivers.
The proposed Multicast Reserved BW Allocation (MRBA) protocol allocates part of the BW in the links only to multicast sessions. Simulation results show the increase in
the overall level of Receiver Satisfaction in the network.

This thesis describes a resource discovery technique in mobile ad hoc networks.
Resource discovery is technique to search data in among the mobile nodes in the network.
The highly dynamic nature of the infrastructure-less ad hoc networks poses new
challenges in resource discovery, thus there is a need to for an optimized resource
discovery technique. Efficient resource discovery algorithm discovers the resources in a
mobile ad-hoc network in an optimized way. As there is no pre-established infrastructure
in the network, every node takes its decision in forwarding resources and every node
dynamically ranks these resources before disseminating them in the network. Ranking of
the resources spreads the data which is of high priority at that instance of time. Ranking
avoids the spreads the unwanted or low priority data which will utilize the bandwidth
unnecessarily. The efficient resource discovery algorithm also keeps a check that
redundant information is not spread in the network with the available bandwidth and the
bandwidth is utilized in an optimized manner. We then introduce brokers in the algorithm
for a better performance. We present a technique to maintain a constant number of
brokers in the network. Our simulations show that, in a network with high density, the
efficient resource discovery algorithm gives a better performance than the flooding and
rank based broadcast algorithms.

Lower prices of video sensors, security concerns and the need for better and faster
algorithms to extract high level information from video sequences are all factors which
have stimulated research in the area of automated video surveillance systems. In the
context of security the analysis of human interrelations and their environment provides
hints to proactively identify anomalous behavior. However, human detection is a
necessary component in systems where the automatic extraction of higher level
information, such as recognizing individuals' activities, is required. The human detection
problem is one of classification. In general, motion, appearance and shape are the
classification approaches a system can employ to perform human detection. Techniques
representative of these approaches, such us periodic motion detection, skin color
detection and MPEG-7 shape descriptors are implemented in this work. An infrastructure
that allows data collection for such techniques was also implemented.

In mobile ad hoc networks, it is challenging to solve the standard problems
encountered in fixed network because of the unpredictable motion of mobile nodes.
Due to the lack of a fixed infrastructure to serve as the backbone of the network, it
is difficult to manage nodes' locations and ensure the stable node performance. The
virtual mobile node (VMN) abstraction that has been applied implements an virtual
mobile node that consists of a set of real nodes traveling on one predetermined virtual
path to collect messages and deliver them to the destinations when they meet. It
conquers the unpredictable motion with virtual nodes' predictable motion. But it
encounters unavoidable failure when all the nodes leave the VMN region and stop
emulating the VMN. We extend the idea of the VMN abstraction to the Multi-path
Intelligent Virtual Mobile Node (MIVMN) abstraction, which allows the messages
to switch between multiple Hamiltonian paths to increase the message delivery ratio
and decrease the failure rate of the virtual nodes. Through simulation results we
show that the MIVMN abstraction successfully meets our goals.

A variety of classifiers for solving classification problems is available from
the domain of machine learning. Commonly used classifiers include support vector
machines, decision trees and neural networks. These classifiers can be configured
by modifying internal parameters. The large number of available classifiers and
the different configuration possibilities result in a large number of combinatiorrs of
classifier and configuration settings, leaving the practitioner with the problem of
evaluating the performance of different classifiers. This problem can be solved by
using performance metrics. However, the large number of available metrics causes
difficulty in deciding which metrics to use and when comparing classifiers on the
basis of multiple metrics. This paper uses the statistical method of factor analysis
in order to investigate the relationships between several performance metrics and
introduces the concept of relative performance which has the potential to case the
process of comparing several classifiers. The relative performance metric is also
used to evaluate different support vector machine classifiers and to determine if the
default settings in the Weka data mining tool are reasonable.

Mesh-connected multicomputers are one of the simplest and least expensive structures to build a system using hundreds and even thousands of processors. The nodes communicate with each other by sending and receiving messages. As the system gets larger and larger, it not only requires the routing algorithms be efficient but also fault-tolerant. The fault model we use in 2-D meshes is a faulty block while in 3-D meshes, the fault model is a faculty cube. In order to route messages through feasible minimum paths, the extended safety level is used to determine the existence of a minimal path and faulty block (cube) information is used to guide the routing. This dissertation presents an in-depth study of fault-tolerant minimal routing in 2-D tori, 3-D meshes, and tree-based fault-tolerant multicasting in 2-D and 3-D meshes using extended safety levels. Also path-based fault-tolerant deadlock-free multicasting in 2-D and 3-D meshes is studied. In fault-tolerant minimal routing in 2-D meshes, if no faulty block is encountered, any adaptive minimal routing can be used until the message encounters a faulty block. The next step is guided by the faulty block information until the message gets away from the faulty block. After that, any minimal adaptive routing can be used again. The minimal routing in 2-D tori is similar to that in 2-D meshes if at the beginning of the routing a conversion is made from a 2-D torus to a 2-D mesh. The fault-tolerant minimal routing in 3-D meshes can be done in a similar way. In the tree-based multicasting in 2-D and 3-D meshes, a time-step optimal and traffic-step suboptimal algorithm is proposed. Several heuristic strategies are presented to resolve a conflict, which are compared by simulations. A path-based fault-tolerant deadlock-free multicast algorithm in 2-D meshes with inter-block distance of at least three is presented to solve the deadlock problem in tree-based multicast algorithms. The approach is then extended to 3-D meshes and to inter-block distance of at least two in 2-D meshes. The path is Hamiltonian that is only updated locally in the neighborhood of a faulty block when a faulty block is encountered. Two virtual channels are used to prevent deadlock in 2-D and 3-D meshes with inter-block (inter-cube) distance of at least three and two more virtual channels are added if the inter-block distance is at least two.

This thesis describes routing in mobile ad hoc wireless networks. Ad hoc networks are lack of wired backbone to maintain routes as mobile hosts move and power is on or off. Therefore, the hosts in ad hoc networks must cooperate with each other to determine routes in a distributed manner. Routing based on a connected dominating set is a frequently used approach, where the searching space for a route is reduced to nodes in small connected dominating set subnetwork. We propose a simple and efficient distributed algorithm for calculating connected dominating set in a given un-directed ad hoc network, then evaluate the proposed algorithm through simulation. We also discuss connected dominating set update/recalculation algorithms when the topology of the ad hoc network changes. We also explore the possible extension of using hierarchical connected dominating set. The shortest path routing and the dynamic source routing, which are based on the connected dominating set subnetwork, are discussed.

We propose a new minimum total communication distance (TCD) algorithm and an optimal TCD algorithm for broadcast in a 2-dimensional mesh (2-D mesh). The former generates a minimum TCD from a given source node, and the latter guarantees a minimum TCD among all the possible source nodes. These algorithms are based on a divide-and-conquer approach where a 2-D mesh is partitioned into four submeshes of equal size. The source node sends the broadcast message to a special node called an eye in each submesh. The above procedure is then recursively applied in each submesh. These algorithms are extended to a 3-dimensional mesh (3-D mesh), and are generalized to a d-dimensional mesh or torus. In addition, the proposed approach can potentially be used to solve optimization problems in other collective communication operations.