Network Algorithms for Routing and Sensing using Area-preserving Maps, Homology, and Curvatur

With the rise of IoT (Internet Of Things), the algorithms of routing and sensing on network devices have never been more important. Given a series of wireless nodes that might deploy to monitor the temperature in the building, air condition in cities, or forest fire in the wild, a series of wireless nodes require a simple routing algorithm to connect two separate nodes. Meanwhile, since these nodes mostly come with low-cost CPU and with limited battery life, while considering about good routing algorithm, these nodes need to sense and take its environment into serious account for better resource allocation. In decades, most of these challenges have been resolved in general geometric setting such that nodes connect through unit disk graph model, require geo-coordinates for each node and a global view of the domain and so on. To provide a different point of view in network algorithms, in this thesis, we discuss these network algorithms that go beyond the Euclidean structures and focus on the intrinsic properties such as embedding, topology, and curvature.;In the first part, we consider the embedding of the network. We observe that the traffic flow in the network is related to the domain shape and density of the network. By taking advantage of area-preserving map, we are able to map any given domain into a disk domain, which is easy to balance the traffic flow, and hence achieve the goal of load balancing routing in wireless sensor network. More, we study optimal mass transportation theory, which is a special case of area-preserving map, and connect it with the clustering problem and resource allocation problem. To do so, we treat network users as resources with different suppliers, and base stations as factories with different demand, then apply the optimal mass transportation theory to find the optimal solution.;In the second part, we take the topology of the network into account and develop discrete algorithms that can locally detect the topology feature of the network. In one application, we propose homotopic routing in wireless sensor network, which is a routing scheme that finds a path of the specified homotopy. In another application, we extend the idea of path homotopy/homology and use homology as a category for path classification.;In the last part, we introduce the "Ollivier-Ricci Curvature" for the general graph. We show that curvature can act as an attribute of the edges, and are highly related to the robustness and connectivity of the graph. Moreover, since the curvature distribution is unique from graph to graph, it can be seen as graph features and treated as a graph kernel, which greatly helps for graph classification. We also define graph Ricci flow as well as a novel graph metric called "Ricci flow metric", and apply this metric to solve the graph isomorphism problem. Since graph Ricci flow uniformizes discrete Ricci curvature, it induces a Ricci flow metric that is insensitive to node/edge insertions and deletions.