|Computers, Materials & Continua |
Multi-Path Service Function Chaining for Mobile Surveillance of Animal Husbandry
1School of Computer Science and Engineering, Southwest Minzu University, Chengdu, 610041, China
2School of Computer Science, Chengdu University of Information Technology, Chengdu, 610225, China
3School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu, China
4Department of Computer Science and IT, The University of Lahore, Lahore, 54000, Pakistan
*Corresponding Author: Tao Wu. Email: firstname.lastname@example.org
Received: 04 August 2021; Accepted: 07 September 2021
Abstract: Animal husbandry is the pillar industry in some ethnic areas of China. However, the communication/networking infrastructure in these areas is often underdeveloped, thus the difficulty in centralized management, and challenges for the effective monitoring. Considering the dynamics of the field monitoring environment, as well as the diversity and mobility of monitoring targets, traditional WSN (Wireless Sensor Networks) or IoT (Internet of Things) is difficult to meet the surveillance needs. Mobile surveillance that features the collaboration of various functions (camera, sensing, image recognition, etc.) deployed on mobile devices is desirable in a volatile wireless environment. This paper proposes the service function chaining for mobile surveillance of animal husbandry, which orchestrates multi-path multi-function (MPMF) chains to help mobile devices to collaborate in complex surveillance tasks, provide backup chains in case the primary service function chain fails due to mobility, signal strength, obstacle, etc., and make up for the defects of difficult deployment of monitoring facilities in ethnic areas. MPMF algorithm models both mobile devices and various functions deployed on them as abstract graph nodes, so that chains that are required to traverse various functions and hosting mobile devices can be orchestrated in a single graph-based query through modified and adapted Dijkstra-like algorithms, with their cost ordered automatically. Experiment results show that the proposed MPMF algorithm finds multiple least-costly chains that traverse demanded functions in a timely fashion on Raspberry Pi-equipped mobile devices.
Keywords: Service function chaining; orchestration; surveillance; shortest path
Animal husbandry is the pillar industry in some ethnic areas in China. Affected by climate, grazing and other factors, animal husbandry areas often face the problems of grassland degradation, destruction of plants, wandering away of herds, invasion of natural predators, rain and snow disasters, etc., which result in remarkable economic losses. In order to effectively reduce the losses caused by these problems, it is necessary to carry out continuous, long-term and dynamic monitoring over vast gazing lands and wide-spread livestock. However, the communication/networking infrastructure in ethnic areas is often underdeveloped, thus the difficulty in centralized management, and challenges for the effective monitoring.
At the same time, considering the complexity and dynamics of the field monitoring environment, as well as the diversity and mobility of monitoring targets (such as mobile herds, lost individuals, natural enemies, etc.), the requirements of mobility, collaboration and low power consumption are put forward for monitoring devices. Therefore, simply introducing fixed-position sensors/cameras to deploy traditional wireless sensor networks (WSN) [1,2] or Internet of things (IoT) [3,4] is difficult to meet the mobility needs [5–8], so it is necessary to implement the mobile surveillance over gazing lands and livestock in ethnic areas. On the one hand, it requires that the wireless communication mechanism used by mobile monitoring devices should have good robustness, and be able to adapt to bad communication conditions; On the other hand, considering the limited computing power and functions on the devices in the mobile wireless environment, mobile monitoring devices are also required to have the ability to cooperate with each other in more complex surveillance tasks. To briefly summarize, orchestration of functionally diverse monitoring devices plays a key role to fulfill mobile surveillance of animal husbandry, given underdeveloped monitoring and communication infrastructure in ethnic areas. The mobile wireless environment is quite volatile in that the established collaborative relationships (e.g., the hop-by-hop routing) vary over time. Even though chains of mobile devices can be made by orchestration, they might stop functioning or do not function as expected due to mobility, obstacles, signal strength, etc. Therefore, orchestration of mobile devices in wireless environment should consider backup chains in case the primary chain fails. Meanwhile, chains should also reflect the quality in addition to functions, and better ones should be automatically selected as preferred chains.
In order to face these challenges, this paper proposes service function chaining [9,10] for mobile surveillance of animal husbandry, which orchestrates multi-path multi-function chains to help mobile devices to cooperate in complex surveillance tasks.
The rest of this paper is organized as follows. Section 2 introduces the mobile device architecture and functional wireless network topology in an orchestration view. Section 3 gives the formal modeling of the mobile devices’ orchestration. Section 4 specifies the algorithm that solves the MPMF problem. Experiments are conducted in Section 5. Related works are summarized in Section 6. And finally, this paper is concluded and future works are envisioned in Section 7.
2 Mobile Device Architecture and Functional Wireless Network Topology
2.1 Mobile Device Architecture
In order to accomplish the service function chaining of various functions, a mobile device is roughly divided into 3 layers as shown in Fig. 1, namely, from bottom up, HW (hardware) layer, OS (operating system) layer, and orchestration layer, as we can see from Fig. 1. HW layer is the mobile hardware platform. Drones, smart cars, etc., with Raspberry Pi can be chosen to serve this purpose. HW layer provides mobility and various functions, e.g., camera, sensors, etc. We choose smart cars as the hardware platform in this paper. OS layer provides the operating system and basic software capabilities such as network, compute, and storage resources. In this paper, Raspbian OS is chosen to accommodate software capabilities, since it is lightweight and Linux-compatible. Orchestration layer provides two major functionalities, namely, the collector, which collects information such as network topologies, various metrics that reflect performances of mobile devices, etc., and the orchestrator, which accepts service function chaining request and optimally chains demanded functions as per information gathered by the collector. Based on the previous discussion, we give the formal definition of the mobile device in this paper.
Definition 1. The mobile device: The mobile device is defined as , where represents functions deployed on the device ( stands for the -th function on the -th device), such as picture shooting, sensing, etc., and represents qualities of various metrics of the device ( stands for the -th metric's quality on the -th device), such as bandwidth, delay, etc.
2.2 Functional View of the Wireless Network Topology
To orchestrate various functions deployed on mobile devices in a wireless network, one should investigate the functional view of the wireless network topology. Usually, one device is deployed with at least one function, such as photo-shooting, video surveillance, humidity sensing, etc., in addition to data-forwarding, as we can see from Fig. 2. To model functional view compatible with conventional topological view, functions can also be seen as nodes, which are directly connected with the hosting mobile device that are abstracted as nodes themselves. That is to say, functions are virtually one hop away from the hosting device, and are mutually connected through hosting devices, forming a cluster-like structure around the mobile device. Meanwhile, in a decentralized ad hoc wireless network, mutual links between mobile devices are rather temporary due to mobility, obstacles, signal strength, etc. It is usually a multi-hop network from the source to the destination device. Links are effective with devices staying within one another's radio coverage, but ineffective if outside, forming a mesh-like structure where one device could have multiple radio links with others, and communicate with others hop-by-hop. To summarize, the functional view of the mobile wireless network topology, when functions are treated as nodes like mobile devices, is a mesh-cluster structure, which is multi-hop globally for data streams between mobile devices, and single-hop locally for data streams between functions and the hosting device. For orchestration between functions, especially between those deployed on different mobile devices, data streams traverse in a function-device-function-device-function … interleaved manner, similar to service function chaining in NFV-enabled environments. Therefore, the orchestration of various functions can be modeled as service function chaining problem.
For example, in Fig. 2, the blue dashed arrow indicates a service function chain that orchestrates camera, temperature sensor, humidity sensor, and recognition as a “herd food analysis” application, across multiple mobile devices, capable of, collectively, taking photos of and recognizing grass species and conditions in the herd's habitat with perceived temperature and humidity status. Also, a surveillance → recognition → alarm chain can be built as a “natural enemies driving” application that first monitors and recognizes natural enemies, then tries to proactively drive them away with deployed alarming equipment.
Based on the previous discussion, we give the formal definition of the functional mobile wireless network topology in this paper.
Definition 2. The functional mobile wireless network: The functional mobile wireless network is defined as undirected graph , where represents mobile devices, represents all on-device functions, and represents radio links, where can also be depicted as if and can communicate directly, and functional links, where can also be depicted as if has deployed on it.
Every radio link will be assigned with a cost according to 3.1. The cost for a functional link is set to 0. According to the previous definition, mobile devices and functions are all equally treated as nodes in an undirected graph, so that graph theories can be applied for service function chaining to orchestrate function-device interleaved chains in a single graph query.
3 Problem Statement and Modeling
3.1 Cost Evaluation
Note that gathered metrics of a mobile device are usually a vector, including bandwidth, delay, packet loss, etc. To simplify orchestration and reduce the problem dimensions, a vector of metrics can be transformed as a scalar value (i.e., the “cost”), as per the properties of metrics. Let denote the cost corresponding to , i.e., the -th metric of mobile device . We consider the following metrics and their transformation methods, so that they can be evaluated as additive costs to apply Dijkstra-like algorithms for shortest paths-based service function chaining: (1) delay, ; (2) bandwidth, , where is the benchmark bandwidth similar to that in OSPF; (3) packet loss, ; (4) availability, . After transformation, every mobile can be evaluated with a cost function using weighted summation: , where , which is then divided equally to be assigned to its effective physical radio links, i.e., , where is the number of radio links of mobile device , to apply Dijkstra-based algorithms for service function chaining.
3.2 The Orchestration Model
Since mobile devices have limited computing capabilities and functionalities, to accomplish complex surveillance tasks, it might require various functions to be orchestrated as a whole application, so that devices collaborate smoothly. That is, a service function chain consists of multiple functions. Considering the instability and volatility of the wireless network, service function chains have higher probability of failure, thus the necessity of finding multiple chains. Meanwhile, chains should also reflect the quality in addition to functions. Based on these intuitions, we model the service function chaining of mobile devices as multi-path multi-function orchestration as follows.
Definition 3. The Multi-Path Multi-Function Orchestration (MPMF): Given an orchestration request where , and a positive integer K, the MPMF orchestration finds the set , where is the set containing all the chains from to , such that:
• , , , i.e., two consecutive functions are chained by one or more hosting mobile devices.
• , , i.e., a chain must traverse all the functions in the order demanded by .
• , , i.e., no duplicated chain.
• , , i.e., is found before (shorter chains are found earlier).
• , , i.e., only the K least-costly chains are to be found.
4 The Orchestration Algorithm
Intuitively, to solve the MPMF problem is to enumerate all sub-paths ordered by cost between two consecutive functions and , and concatenate them to pick the K least-costly chains as per the order of orchestration request . This is feasible for simpler topologies, but not for more complex topologies with even just tens of mobile devices and a couple of functions per device, since the complexity increases exponentially. Specifically, two major challenges are faced as per the requirements of MPMF. Challenge 1: plain Dijkstra algorithm does not find multiple shortest paths. Besides, the concatenation of sub-paths should also be carefully designed to reduce the problem complexity, other than pure enumeration that could be time-consuming for larger networks. Challenge 2: Dijkstra-like algorithms do not restrain the traversed nodes (i.e., functions in the case of MPMF), thus not applicable for service function chaining. To this end, we combine and improve Dijkstra and KSP (K Shortest Paths) algorithms to solve MPMF problem that requires the K least-costly chains and traversing all demanded functions.
4.1 The Multi-Path Aspect
We firstly cope with challenge 1, i.e., multi-path aspect. Tabs. 1 and 2 show in detail the adapted and modified KSP algorithm, where dsp(,) calculates the shortest path from the source node to the destination node using Dijkstra algorithm. The routine nextPath(,) finds the next shortest path between and using deviation method (see details in Tab. 2). restoreGraph() is used to set the graph back to its initial linkage states after temporary deletion of arcs. is the ordered set that stores the K shortest chains. is the set that stores the shortest chains candidates. Detailed explanations are shown in the comments in Tabs. 1 and 2.
4.2 The Multi-Function Aspect
We then cope with challenge 2, i.e., multi-function aspect. The MFMP algorithm is shown in Tab. 3. It takes as the input the functions required by the service function chaining request which must be traversed. To get the least costly chain that traverses all the demanded functions, the algorithm gets the shortest path for every and function pair along the request . These are the shortest segments that constitute the shortest path and are put into the set, i.e., the shortest segments between and in the chain. Also, the second shortest segments from to are calculated for later iterations. The above is the initialization of the algorithm, shown in lines 3–7.
Concatenating all the new segments in , , ⋅ ⋅ ⋅, generates a new batch of feasible paths from to which are put into . The shortest one from is the next shortest path (shown in lines 14 and 17). The next problem is to determine from which node to generate the next segment so that the next batch paths can be found. Since the algorithm invokes nextPath() routine, it is guaranteed the last one in is the longest of currently found shortest segments from to . All the .getLast() are compared to pick the shortest segment, then the corresponding is the node to derive new segments, i.e., the deviation node (shown in lines 15 and 18). In this way, the algorithm does not have to derive new segments from every node in the next iteration; it only derives new segment from deviation node, thus time complexity is minimized. The above is the main loop of the algorithm, shown in lines 12–19.
We conduct service function chaining in a wireless network consists of tens mobile devices, each with 5 functions (commonly seen functions in animal husbandry, e.g., surveillance, sensing, etc.), implemented on the smart cars with Raspberry Pi and Raspbian OS. These mobile devices were networked through the methods proposed in our previous work . The orchestrator, i.e., the MPMF algorithm, and the collector are implemented in its orchestration layer (see Fig. 3).
Several counterparts capable of service function chaining with necessary modifications, CPSPARQL [12–14] and Virtuoso (discussion on them can be found in Section 6), are compared with MPMF. The experiments are conducted in two wireless networks, containing 10 and 20 mobile devices respectively, and the results are shown in Figs. 4a and 4b, where the suffix “-x” in the legends indicates the number of functions in a service function chaining request, i.e., how many functions to be traversed by a chain. All counterparts are evaluated by chaining time in ms (the y-axis) when finding K different chains (the x-axis). MPMF conducts chaining by means of deviation method. That is, based on the current shortest path, the most appropriate node is selected, from which there derives a new shortest path that traverse all the required functions, instead of enumerating all the possible paths. In this way, the K least-costly paths are found and ordered one by one without enumeration. This, at large, saves chaining time. As we can see from the figure, MPMF scales almost linear to the number of functions demanded by the request and the number of chains to be found. And its performance is time-efficient. For the scenario of 10 mobile devices, it takes about 200 ms for MFMP to find 5 chains that traverse 6 functions, among which the shortest one is used as the primary chain and others stand by as backups in case of any failure or malfunction of the primary one. It takes about 475 ms to accomplish the same task for the 20 mobile devices. See orange lines in Figs. 4a and 4b.
CPSPARQL takes similar philosophy to our work, to compose service function chains, though different in techniques. That is, CPSPARQL finds and orders the K least-costly chains gradually. Notice that the performance of CPSPARQL is less-efficient with regard to time consumed. One major reason for this is that CPSPARQL uses more redundant data structures of RDF (Resource Description Framework) triples because the primary usage of CPSPARQL is in the field of Semantic Web, where, usually, data are stored as half-structured triples. Triples take the form of three ordered entities, i.e., [subject → predicate → object], where edge-similar predicates are also modelled as nodes, increasing the size of abstract graph. Expressive enough for triples though, to express a simple relationship using triples, it adds more nodes and edges in the abstract graph, which as a result lowers the performance with regard to time complexity, especially when applied in the orchestration of more complex wireless networks. Therefore, RDF triples might be heavyweight in this scenario. It takes about 354 ms for CPSPARQL to find five 6-function chains in the scenario of 10 mobile devices, and 980 ms in the scenario of 20 mobile devices. See purple lines in Fig. 4a and 4b.
Virtuoso is also a high-efficient Semantic Web query engine that provides good performance to search useful information in RDF triples. Virtuoso takes a different technical path that enumerates all possible chains that traverse all required functions, and order them in one shot. This is feasible when the network size is small. We can see from Fig. 4a that, Virtuoso, with good optimization of implementation, even outperforms MPMF and CPSPARQL in the scenario of 10 mobile devices, although seemingly time-consuming enumeration strategy is taken. That is, it takes only about 150 ms to find five 6-function chains, superior to MPMF and CPSAPRQL. One thing worth noticing is that Virtuoso provides the same temporal performance for different K (i.e., the number of service function chains) because it enumerates all chains. That is, K is irrelative for Virtuoso. However, in the scenario of 20 mobile devices, the performance of enumeration degrades considerably. To accomplish the same task, it takes about 1385 ms. See green lines in Figs. 4a and 4b.
To summarize, MPMF provides good performance for service function chaining that orchestrates various functions deployed on mobile devices. Therefore, this algorithm is a fitting candidate for the potential usage in the mobile surveillance of animal husbandry in ethnic areas.
6 Related Works
Service function chaining is an active research area in recent years. Reference  proposes the low-latency and resource-efficient service function chaining orchestration in network function virtualization (NFV) . However, it does not suit well in the context of wireless orchestration, nor does it find multiple chains to as backups in case the primary one fails in a volatile environment. StEEIRNG  tries to arrange a path traversing specific middleboxes by extending the OpenFlow and NOX controller, suitable for service function chaining in the context of SDN (Software-Defined Networking) [18,19]. The key of the extension is the split of a monolithic flow table into several micro tables to constrain the “rule explosion”. StEEIRNG solve the path planning problem using Graph Theory. The main deficiency of StEEIRNG is the lack of QoS support. It conducts the chaining mainly based on middleboxes functions. SlickFlow  focuses on the source routing (similar to service function chaining) based fault recovery. The fault recovery application on the controller pushes the path information as special headers on the ingress switches. The path consists of several segments where next hop and the alternative path from that hop are contained in each segment. Upon network failure at a certain node, alternative path is adopted proactively by the current node to reduce controller intervention. Reference  considers the service function chain orchestration in a network slice across multiple domains. Reference  also considers a similar energy-efficient and traffic-aware service function chaining orchestration in multi-domain networks, which is formulated as an integer linear programming (ILP) model to find an optimal solution. A low-complexity heuristic algorithm is derived to chain VNFs across multiple domains.
We can see that recent works in service function chaining mainly focus on the wired network scenarios, as opposed to wireless networks. Therefore, these works do not fit well in the context of wireless orchestration with node mobility that increases the instability and volatility. Our work differs from these works in that we consider multiple backup chains in case of chain failure due to various factors in wireless networks.
CPSPARQL and Virtuoso, although they originate from the Semantic Web field, can be applied for chaining purposes with necessary modifications and adaptations. Nevertheless, their performances are not as good as expected in mobile device orchestration, due to their RDF-based data structures (i.e., triple-like) contains redundant nodes and edges that compromise the performance in case of more complex networks.
To implement mobile surveillance for animal husbandry in ethic areas of China, where communication or networking infrastructure is less-developed, this paper proposes the multi-path service function chaining, which orchestrates multiple chains with the least costly one as the primary chain and several others as backups, to accommodate wireless volatility and instability. The proposed MPMF algorithm performs well in the orchestration in wireless networks with tens of mobile devices.
In this paper, the quality of chains is evaluated by a scalar, i.e., the cost. It can be understood as a “best effort” service, since no quality constraints are imposed , i.e., no restriction on delay, bandwidth, packet loss, etc. If multiple constraints in addition to quality preference are put forward for service function chaining, the complexity becomes high. We will study the possibility of applying reinforcement learning in the field of wireless service function chaining in the future work, to provide an efficient and topology-adaptive service function chaining framework with self-learning capabilities.
Acknowledgement: The authors would like to thank the time and efforts by the editors and reviewers.
Funding Statement: This research was partially supported by the National Key Research and Development Program of China (2018YFC1507005), China Postdoctoral Science Foundation (2018M643448), Sichuan Science and Technology Program (2020YFG0189), and Fundamental Research Funds for the Central Universities, Southwest Minzu University (2020NQN18).
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
|This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.|