Ana Cristina

Kochem Vendramin

Anelise Munaretto
email: anelise@utfpr.edu.br.

Myriam Regattieri Delgado
email: myriamdelg@utfpr.edu.br.

Aline Carneiro Viana

Mauro Fonseca
email: maurofonseca@utfpr.edu.br.

A Social-Aware Routing Protocol For Opportunistic Networks

Keywords: cultural algorithms, ant colony, social analysis, forwarding protocol, intermittently connected networks

This work proposes the Cultural Greedy Ant (CGrAnt) protocol to solve the problem of data delivery in opportunistic and intermittently connected networks referred to as Delay Tolerant Networks (DTNs). CGrAnt is a hybrid Swarm Intelligence-based forwarding protocol designed to address the dynamic and complex environment of DTNs. CGrAnt is based on: (1) Cultural Algorithms (CA) and Ant Colony Optimization (ACO) and (2) operational metrics that characterize the opportunistic social connectivity between wireless users. The most promising message forwarders are selected via a greedy transition rule based on local and global information captured from the DTN environment. Using simulations, we first analyze the influence of the ACO operators and CA knowledge on the CGrAnt performance. We then compare the performance of CGrAnt with the PROPHET and Epidemic protocols under varying networking parameters. The results show that CGrAnt achieves the highest delivery ratio (gains of 99.12% compared with PROPHET and 40.21% compared with Epidemic) and the lowest message replication (63.60% lower than PROPHET and 60.84% lower than Epidemic).

Introduction

The pervasiveness of computing devices and the emergence of new applications and cloud services are factors emphasizing the increasing need for adaptive networking solutions. In most cases, this adaptation requires the design of interdisciplinary approaches as those inspired by nature, social structures, games, and control systems. The approach presented in this paper brings together solutions from different, yet complementary domains, i.e., networking, artificial intelligence, and complex networks, and is aimed at addressing the problem of efficient data delivery in intermittently connected networks.

As mobile devices become increasingly powerful in terms of communication capabilities, the appearance of opportunistic and intermittently connected networks referred to as Delay Tolerant Networks (DTNs) is becoming a reality [START_REF] Khabbaz | Disruption-tolerant networking: A comprehensive survey on recent developments and persisting challenges[END_REF][START_REF] Chaintreau | An improved ant-based algorithm for the degree-constrained minimum spanning tree problem[END_REF][START_REF] Tournoux | Density-aware routing in highly dynamic dtns: The rollernet case[END_REF]. In such networks, contacts occur opportunistically in corporate environments such as conferences sites, urban areas, or university campuses.

Understanding node mobility is of fundamental importance in DTNs when designing new communication protocols that consider opportunistic encounters among nodes. In fact, it is well known in the literature that the movement of nodes in such networks is not random and is a manifestation of their routine behavior and intentions [START_REF] Gonzalez | Understanding individual human mobility patterns[END_REF]. Together with contact-based interactions among nodes, this movement generates a mobile social network. The analysis of such mobility patterns and the understanding of how mobile nodes interact (i.e., wirelessly encounter) play a critical role in the design of solutions for DTNs.

On the other hand, given that adaptation in nature is a permanent and continuous process, we note that the dynamic and complex environment of DTNs favors the application of Swarm Intelligence (SI) methods, including approaches based on Ant Colony Optimization (ACO) [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF] and Cultural Algorithms (CAs) [START_REF] Reynolds | An introduction to cultural algorithm[END_REF]. In fact, the environment of opportunistic DTNs presents certain features in the mobility patterns of the network nodes that can be sufficiently explored by joining CA and ACO (e.g., knowledge stored in the belief space can guide the swarms through new or already constructed paths depending on the node behavior).

Motivated by those issues, this paper proposes the use of a Cultural Greedy Ant routing protocol, known as CGrAnt, to identify the most promising social-aware forwarders in DTNs, while profiting from SI-based paradigms.

For this approach, the opportunistic and complex information (such as frequency and duration, centrality metrics, or mobility features) with respect to physical encounters between mobile nodes is gathered and favorable paths along which to forward each message are determined, while limiting data redundancy. Hence, the forwarding approach implemented by CGrAnt is adaptive and designed to match forwarding decisions to different mobility and operating conditions. Using a simulation environment, we evaluate the performance of CGrAnt under varying parameters, i.e., movement models, buffer sizes, message TTLs, simulation times, communication ranges, and transmission rates. The results confirm the satisfactory behavior of our routing protocol in key performance metrics, such as: message delivery ratio, message redundancy ratio, and message delivery delay.

The remainder of this paper is structured as follows. Section 2 provides an overview of the principles that drive our approach and its application environment. Section 3 describes the CGrAnt routing protocol in detail, and Section 4 presents the simulation environment. Sections 5 and 6 investigate how the proposed operational metrics and components affect the CGrAnt's performance. Section 7 compares the performance of CGrAnt with two known DTN forwarding protocols under varying networking parameters, and finally, Section 8 summarizes the concluding remarks and future directions.

Rationale and Background

This section begins with an overview of the addressed problem. The main innovations and contributions are further discussed, and the state-of-the-art of forwarding in DTN environment is described, with particular attention given to approaches based on SI.

Problem overview

In DTNs, a fully connected multi-hop path may not exist between a sender and a receiver due to either mobility issues or varying conditions of wireless communications, thus requiring the use of specific mechanisms to ensure robustness in the data communication among nodes. The information exchange must be performed in an opportunistic fashion through so-called carry-and-forward routing techniques [START_REF] Cerf | Delay-Tolerant Network Architecture[END_REF]. The nodes may need to store messages from other nodes in their buffers for long periods of time and carry these messages until a forwarding opportunity arises [START_REF] Cerf | Delay-Tolerant Network Architecture[END_REF]. Additionally, message replication may be necessary to increase the probability of successfully delivered messages. However, certain problems exist in a limited resource scenario: replications are undesirable because they compete with valid data messages in the paths toward a destination, and the storage of neighbors' data messages can be a problem due to limited buffer sizes.

The problem of routing in DTNs can thus, be modeled as a multimodal optimization problem attempting to find not just one solution but a set of solutions (i.e., multiple paths between two nodes). The finite set of possible solutions (i.e., paths formed by a sequence of nodes in which each node permutation generates a new solution) characterizes the routing in DTNs as a combinatorial problem. The problem can be also modeled as a dynamic state because the search space characteristics and the location and value of the solutions will change over time. The problem of routing in DTNs presents, therefore, a complex challenge, with several aspects still unexplored by most approaches described in the literature. Therefore, an updated consideration of the DTN dynamics is necessary and can be accomplished by periodically analyzing the neighbor information and selecting more than one path along which to forward each message while limiting message redundancy. The dynamicity and complex premises of DTNs characterize it as an environment favorable for the application of SI algorithms, including ACO and CA [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF][START_REF] Reynolds | An introduction to cultural algorithm[END_REF].

CGrAnt in a Nutshell

In view of the problem discussed in the previous session, we propose the CGrAnt protocol as a solution to the problem of identifying a set of good nodes along which to route each message in DTNs. To increase the reliability in such dynamic networks, choosing the best path for routing of messages should not be the main goal of a routing protocol. Indeed, it is equally important to maintain a diversity of paths and avoid convergence to only one or a few solutions.

CGrAnt can be defined as a hybrid SI system based on (1) CA and ACO and (2) operational metrics that characterize the opportunistic social connectivity between nodes. To adapt to the large topology variations encountered by a DTN and to reduce latency in message delivery, the following modifications are incorporated into CGrAnt that differentiate it from traditional SI-based protocols. (1) The SI control messages named Forward Ants (FAs), responsible for the path construction, are encapsulated into the data messages. (2) The number of FAs created and forwarded is dynamically defined according to the knowledge stored in the nodes. (3) CGrAnt adopts a greedy ACO transition rule that is similar to the deterministic transition rule proposed in the Ant Colony System (ACS) [START_REF] Dorigo | Ant colony system: A cooperative learning approach to the traveling salesman problem[END_REF].

Nevertheless, instead of using both probabilistic and deterministic rules as in ACS, CGrAnt uses only the greedy transition rule, which considers the heuristic function and/or pheromone concentration, to forward messages to the most promising node(s), and/or to exploit previously found good solutions. The search space exploration is still provided by the DTNs dynamics.

(4) Instead of using time-based pheromone evaporation, CGrAnt performs an event-driven evaporation, which only occurs if a node detects that a new path toward a destination has been found. Thus, allowing redundant paths becomes more important than converging to the best path. (5) Because there is no central element in DTNs, the knowledge stored in the CA belief space is distributed among network nodes. ( 6) The information exchanged between the belief and population spaces always occurs in a distributed manner intermediated by the CGrAnt operational metrics. The ACO and CA modifications seem more adapted to intermittently connected networks such as DTNs, yet a subset may allow CGrAnt to operate in different dynamic scenarios.

Related work

We go through the related work in the area, discussing the most representative results on both DTN forwarding protocol and swarm intelligence methods.

DTN Forwarding protocols

The most common solutions in the literature take a controlled flooding approach. For instance, epidemic routing provides an optimal solution in terms of message delivery and latency, when no buffer constraint is present [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF]. In Epidemic routing, a node buffers a message and passes it on to all encountered nodes that have not received it before. No good message forwarders prediction is performed. To limit resource utilization, a hop-count field can be set in each message. Epidemic routing is simple and provides high reliability and adaptability, but it might generate too many redundant messages, wasting communication and battery resources. To reduce this overhead, the Spray and Wait approach [START_REF] Spyropoulos | Spray and wait: An efficient routing scheme for intermittently connected mobile networks[END_REF] sprays messages over different contacts and then wait for these contacts to eventually deliver the message to the destination.

Predicted-based approaches try to reduce the message overhead by selecting a few good relays. In this context and more related to CGrAnt, several approaches estimate a delivery likelihood based on the frequency or similarities of meeting with contacts like PROPHET [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF], Delegation Forwarding [START_REF] Erramilli | Delegation forwarding[END_REF], and Spray and Focus [START_REF] Spyropoulos | Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility[END_REF]. In particular, in PROPHET, vectors are exchanged that indicate the predictability of each node in delivering their messages. This predictability increases every time two nodes come into contact and reduces if they fail to meet frequently. When a node A establishes a contact with a node B, a message will be sent to B if its message delivery's prediction is higher as compared to A. The delivery predictability also has a transitive property. All these approaches, however, might be too conservative and lose good forwarding opportunities in environments with scarce connectivity.

Most importantly, the majority of the approaches assume infinite buffers and bandwidth.

Other approaches study the effect of social networking on data forwarding. BubbleRap [START_REF] Hui | BUBBLE Rap: Social-based forwarding in delay tolerant networks[END_REF] and SimBet [START_REF] Daly | Social network analysis for routing in disconnected delay-tolerant MANETs[END_REF]) use information about social community structures and popularity within a community to choose good relays. [START_REF] Zhang | Social-aware data diffusion in delay tolerant manets[END_REF] introduce four social-aware data diffusion schemes based on the social relationship and data similarity of the contacts.

Differing from such protocols, CGrAnt conducts local and global searches and gathers relevant information from the DTN nodes. CGrAnt can thus analyze the utility of each node as a message forwarder and limit message replications.

Swarm intelligence methods

Though ACO has been extensively used in network environments, especially in MANETs [START_REF] Liu | Swarm intelligence based node-disjoint multi-path routing protocol for mobile ad hoc networks[END_REF][START_REF] Rosati | On ant routing algorithms in ad hoc networks with critical connectivity[END_REF], routing in DTNs is challenging and few ACO protocols have been proposed. DAR [START_REF] Rosati | On ant routing algorithms in ad hoc networks with critical connectivity[END_REF] does not consider local information from neighboring nodes and uses only the pheromone global information, which is not always available in DTNs. ABMF [START_REF] La | Ant-based adaptive message forwarding scheme for challenged networks with sparse connectivity[END_REF] only aims to estimate the extra capacity of each node as a message forwarder depending on its buffer dy-namics. ACRP (Zhang et al., 2010b) uses the Epidemic protocol to flood the network with control messages associated with Forward Ants (FAs) and Backward Ants (BAs). None of the mentioned approaches consider the following important aspects of sparse and opportunistic networks: (i) analyzing social metrics of nodes, including their degree and betweenness centralities to aid select message forwarders; (ii) preventing the loss of previously found good paths caused by pheromone evaporation processes that are periodically performed (i.e., based on time, as in ABMF and ACRP) or the overuse of those paths due to the absence of an evaporation process (as in DAR); and

(iii) dynamically limiting the number of control and data messages forwarded in the network. [START_REF] Ma | Research on cultural algorithm for solving routing problem of mobile agents[END_REF]Zhang et al., 2010a) use CA for performing routing in a static topology with service quality constraints. They, however, operate in a static environment and do not analyze the dynamics of the contacts in a social network to determine opportunities. Moreover, they search for a single optimal path with a set of constraints and use Situational and Normative knowledge only to increase the convergence speed. Finally, they use a single and centralized belief space.

Considering these issues, we proposed a first version of the SI-based routing protocol for DTNs that used only ACO (Vendramin et al., 2012b).

Guided by pheromone concentration, heuristic functions, and social metrics, the Greedy Ant (GrAnt) protocol performed better than the well-known DTN routing protocols (Vendramin et al., 2012b).

CGrAnt encompasses CA and ACO metaheuristics and can be considered as an extension of our previous method (Vendramin et al., 2012b). CGrAnt improves the learning process and the gathering, during evolution, of highlevel information to be stored in the CA belief space.

The CGrAnt Routing Protocol

As previously mentioned, the CGrAnt routing protocol is based on CA and ACO meta-heuristics. CA is comprised of two spaces: (1) Belief Space, which represents the knowledge (i.e., set of information) gathered during the search for a set of paths and (2) Population Space, which is composed of individuals (i.e., ants) looking for solutions (i.e., forwarding paths) in an ACO framework.

In DTN, due to the lack of central element capable of storing and publishing all gathered information, the CGrAnt components are distributed among The next sections describe the CGrAnt routing protocol in detail. Sections 3.1 to 3.3 describe the components used by CGrAnt that influence the search for paths. Sections 3.4 and 3.5 describe the routing phases of CGrAnt, which determine the route(s) a message must follow to reach its destination.

Metrics and Indicators

The communication between the belief and population spaces is mediated by specific metrics and indicators. The metrics incorporated into CGrAnt are classified as basic (obtained directly from the population space or nodes) or composite (obtained from manipulating basic metrics). The basic metrics are classified into local (associated with each node and its neighboring nodes)

and global (associated with complete paths constructed by ants) categories.

Figure 2 illustrates the metrics and their relationships with the belief space stored in each node. The Situational and History knowledge influence the population space and the population space update the global metrics.

Table 1 provides a brief description of the metrics and variables used throughout this paper.

The Local Basic Metrics used by CGrAnt include the following:

• Frequency of Encounters (F E n,d
) between a pair of nodes n and d;

• Duration of an Encounter (DE n,d ) between n and d;

• Average Pause Time (P T n ) in the places visited by n;

• Average Movement Speed (M S n ) of a node n;

• Degree Centrality (DC n ) of a node n [START_REF] Freeman | Centrality in social networks: Conceptual clarification[END_REF]. As n encounters more nodes in the network and increments its degree centrality, it has more opportunities to choose the best message forwarders;

utility is updated, BU n,d (t) = BU n,d (t -1) + 1.
The Composite Metrics of CGrAnt include the following:

• Social Proximity (SP n,d ) between n and d is directly associated with the ACO local operator Heuristic Function (η) and is defined as that compose a path to d m :

SP n,d = F E n,d × DE n,d ; • Path Quality (Q p k sm,dm ),
Q p k sm,dm (t) = ∀n∈p k sm,dm DC n (t) |p| k sm,dm + 1 |p| k sm,dm (1)
The Path Quality metric is directly associated with the ACO global operator Pheromone Concentration (τ );

• Utility of a node n in relation to d (U n,d ), which describes how well n can perform as a message forwarder to d. The U n,d is subsequently determined according to the basic metric RD i,m :

U n,d (t) = η n,d (t) if RD i,m = s m η n,d (t) + τ (i,y),d (t) otherwise, (2)
The

y = d m if n = i j if n = j, (3)
• Stagnation Degree (SD n ) of a node n, which allows the identification of the most mobile nodes in a dynamic scenario (e.g., buses or vehicles) and consequently, adapts CGrAnt to heterogeneous networking encounters on the fly. For this, SD n considers the node average pause time (P T n ) and average movement speed (M S n ):

SD n (t) = P T n M S n (4)
• Stagnation Degree of the social network (SD i J ) of a node i, which is based on the SD n metric:

SD i J (t) = 1 |J| j∈J SD j (t), ( 5
)
where J is the set of nodes encountered by node i;

• Betweenness Utility of the social network (BU i J,d ) of a node i in relation to d, which considers the basic metric BU n,d . The BU i J,d is initialized differently depending on the origin of the BA that announces to i that a complete path to d has been constructed:

BU i J,d (0) = BU i,d (t) if BA came from d BU j,d (t) if BA came from j (6)
The BU i J,d metric is updated with BU i,d whenever i receives a BA.

When the BA comes from a neighboring node j (not from d), BU i J,d is also updated with BU j,d :

BU i J,d (t) =            Z if BA came from d 1 2 (Z + BU j,d (t)) if BA came from j, (7)
where

Z = 1 2 BU i J,d (t -1) + BU i,d (t) .
More details on the metrics definitions are discussed in [23].

In addition to the basic and composite metrics, CGrAnt uses two indicators: (1) best fwd m , which stores the current best forwarder for a specific message m and (2) search status, which decides whether FAs must explore or exploit the network while seeking solutions for the DTN forwarding problem.

Population Space

The population space is composed of FAs and BAs messages. The FAs look for sets of possible paths, i.e., one set P m for each pair (s m , d m ). Assuming a total of M messages to be forwarded in the entire network, there will be several paths sets

{P 1 , • • • , P m , • • • , P M } constructed simultaneously.
Every paths set P m represents a group of solutions generated whenever a message m originated in s m must be sent to d m . Each complete path p in P m composed of a sequence of nodes is established when ant k reaches d m and can be defined as:

p k sm,dm = {s m , • • • , n, • • • , d m }, k = 1, • • • , K m .
For each node i with a message m, each time a better forwarder j for m appears, a new FA k is generated to begin its path construction, and a copy of m is sent to j. The partially constructed path from s m to j remains the same. However, from j, the FA k is free to find d m passing through different nodes n and can provide a different path into the population space. The K m defines the number of FAs generated to find solutions for m. In general,

| P m | K m because a subset of ants cannot find d m .
The parameter K m is dynamically defined according to the belief space knowledge and message delivery success. Ant generation is thus auto-adaptive, as is the number of constructed paths, and both depend on the DTN dynamics.

Belief Space

In CGrAnt protocol, there is no element to centralize and share the gathered knowledge. The belief spaces are thus distributed over the network.

Each belief space in a node encompasses three types of knowledge: Domain, History, and Situational, as detailed hereafter. The Acceptance Function accepts information on the local dynamic of each neighboring node j, only if SD j ∈ (0, ∞). After accepting a new solution, the Update Function is called. It considers the event window W (t) containing a list of local events of i, such as an encounter between i and a non-stationary node j.

The Update Function adds the pair (SD j (t), j) to the list and updates SD i J according to Eq. 5.

The Influence Function evaluates the stagnation degree of i with respect to its social network:

• High stagnation degree: A node i is characterized as a highly stagnated node when the following relations apply:

SD i > SD i J + V s and SD i J ∈
(0, ∞). In this case, its improvement stagnation direction dr i is set to

dr i = +1;
• Low stagnation degree: A node i has a low stagnation degree when the following relations apply: SD i < SD i J -V i and SD i J ∈ (0, ∞) hold. In this case, dr i = -1;

• Medium stagnation degree: A node i is characterized as a medium stagnation node when the previously described relations do not apply. In this case, dr i = 0.

The V i and V s respectively define the decrement and increment in SD i J used to define the range of nodes with medium stagnation degree.

Based on dr i , the Influence Function changes the value of the search status indicator, which aids in defining whether an FA in node i must be sent to exploit or explore during the search for a solution of the DTN forwarding problem.

History Knowledge

introduced to adapt CGrAnt to changes in the network, thus increasing the ability to reflect the global network dynamics. This knowledge stores a history of important past events (in this case, the information that complete paths to d have been found). Due to the lack of a central component, the complete paths cannot be stored in the History knowledge. The betweenness utility metric (representing the partial information of a complete solution)

is subsequently used and may subsequently influence the path search. The History Knowledge is distributed among the network, His i , for i = 1, ..., N .

In each node i, this knowledge is divided in a total of D i sub-knowledge:

His i (t) = {His i,1 (t)
dr j = -1, if BU j,d < BU i J,d ; or dr j = 0, if BU j,d = BU i J,d .
Based on these directions and the search status indicator, the history knowledge influences the message forwarding by deciding whether an FA should be sent through a previously found path and thus exploit the path search.

Situational Knowledge

introduced in CGrAnt to provide a memory of the best solutions, and to influence the search process for a set of paths through these solutions.

Its memory is partial instead of complete and is represented by the best forwarder of each message. The Situational Knowledge is distributed among the network nodes: Sit i , for i = 1, ..., N . In each node i, the Situational knowledge is divided in a total of M i sub-knowledge:

Sit i (t) = {Sit i,1 (t), ..., Sit i,m (t), ..., Sit i,M i (t)},
where M i represents the number of data message m stored in node i's buffer.

Message Forwarding Phase

The message forwarding phase in CGrAnt is initialized on-demand when a message m stored in a node i must be delivered to d m , as described by Algorithm 1. The FAs are subsequently created, encapsulated into m, and sent toward d m via one or more neighboring nodes j.

During message forwarding, an FA at a node i decides whether to forward m to a new neighbor j according to the influence of the three types of knowledge stored in its belief space: Domain, History, and Situational.

Because node i is the first candidate solution for forwarding message m, its identification and utility initialize the Situational knowledge (lines 9 and 10). The decision on forwarding m to j may be to explore (i.e., it is not required that j has previously participated in a path to d m ) or exploit (i.e., j has previously participated in a path toward d m ). The decision is guided by the information on i in terms of RD i,m and SD i stored in Dom i . The status is initialized, enabling both exploitation and exploration of the path search space (lines 12 and 13). These conditions can change in two situations: (i)

i is an intermediate node with a medium stagnation degree (in this case, After analyzing the utility of every current neighbor j and inferring the best choice, CGrAnt sends m to the designated forwarder (lines 33 and/or 44).

In addition to the data message forwarding, control messages are periodically and locally exchanged between i and its neighboring nodes j to update When an FA (along with m) reaches d m , the final quality of the constructed path (Q p k sm,dm ) is calculated as in Eq. 1. After calculating the quality of each new and complete path p, a new control message, the BA, is created from the information obtained by the FA, and the FA is deleted.

Backward Phase

During the backward phase, the BA returns to the node that originated the message m through the reverse path selected by the FA. The concept of using a reverse path in DTNs is motivated by wireless social networks in which (i) individuals are often linked by a short chain of acquaintances, (ii) certain encounters show repetitive behavior, and (iii) nodes have routines that result in frequently visited locations and encounters.

In the reverse path, receiving a BA sent from node y to each neighboring node i produces three effects: (1) increasing the BU i,d value by one;

(2) initializing or updating the BU i J,d value according to Eq. 6 and 7, an effect that corresponds to the Update Function of the History Knowledge; and (3) updating the pheromone concentration toward d according to:

τ (i,y),d (t) = (1 -ρ) × τ (i,y),d (t -1) + Q p k sm,dm (t), (8)
where τ (i,y),d (t -1) is the pheromone on link (i, y) that was last updated at time (t -1). The evaporation process (1 -ρ) is necessary for the ants "to forget" the previous pheromone values deposited on a link to a specific d.

This evaporation reduces the influence of the path search history. When the pheromone is updated, all concentrations that belong to d are evaporated in i.

Even if the BA does not reach the node that originated the message Additionally, the BA serves as an acknowledgment that m has achieved d m , allowing the nodes that still maintain m to delete it and its associated variables. A node that encounters another node that has already received a BA for a given data message also deletes the corresponding message and its associated variables. When the source node receives it, the BA is deleted.

Full paths are thus constructed for each destination using the information gathered by the ants during the path search phase.

Evaluation Methodology

This section describes the numerical analysis we conducted using the Opportunistic Network Environment (ONE) Simulator [START_REF] Keränen | Simulating mobility and DTNs with the ONE[END_REF] to investigate the benefits of the metrics and components incorporated into our proposal. Using ONE we can also assess both performance and accuracy of the CGrAnt protocol in simulation scenarios that consider two different movement models: Working Day (WD) [START_REF] Ekman | Working day movement model[END_REF] and Points of Interest (PoI) [START_REF] Keränen | Simulating mobility and DTNs with the ONE[END_REF], both proposed by default in the ONE simulator. The ONE default parameters were kept unchanged (whenever possible) in order to confirm the results when compared with the others two evaluated protocols (Epidemic and Prophet). Moreover, using the default parameters, we intend to facilitate the dissemination of our proposal in the simulation platform.

The WD movement model represents an activity-based environment that simulates the daily lives (activities) of people who go to work in the morning, spend the day working, may go to a public place for leisure activities with friends at the end of day, and return to their houses at night. In WD, the total area (10, 000 × 8, 000 m 2 ) encompasses meeting points, buses, houses, In the PoI movement model, the total area (8, 800 × 7, 800 m 2 ) is divided into five points of interest that simulate several communities of people who eventually meet each other and exchange data. There are eight groups of nodes (W1, X1, Y1, Z1, W2, X2, Y2, and Z2), each with different destination selection probabilities. The POIs movement model is similar to the community model used by A. Lindgren et al. [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF].

Groups W1, X1, Y1, and Z1 contain 30 nodes each. Groups W2, X2, Y2, and Z2 have five nodes. Every node has one home PoI that is more likely to be visited than the other PoIs; there is a high probability that nodes meet each other within their same home community and a low probability that they go to PoIs outside their home community. The nodes select a destination, move in this direction (with M S ∈ [0.5, 1.5] m/s), wait during a pause time (P T ) ranging from 100 to 200 seconds (for groups W1-Z1) or 4,000 to 5,000 seconds (for W2-Z2), and select the next destination, among other actions. Table 2 shows the settings and communication parameters applied in all experiments for the three protocols under comparison. Unless otherwise described, the parameters used in both scenarios are emphasized in Table 2.

In Section 5, we evaluate the CGrAnt performance with variations in the setting parameters. We analyze the CGrAnt performance in the PoI scenario in terms of the percentage of messages delivered to destinations.

The setting parameters emphasized represent those that provide the best results for the CGrAnt protocol. Next, in Section 6, we investigate a subset of the CGrAnt components by evaluating the protocol performance for both scenarios (WD and PoI). Section 7 compares CGrAnt with the Epidemic and PROPHET protocols in both scenarios and considers different aspects of the communication network context. In all experiments, each message has a size of 500 KB representing its payload and includes an FA with 8 bytes representing its path quality. The BA size is 100 bytes on average (including the header, path quality, and path hops).

The results discussed in Sections 5, 6 and 7 are presented in terms of mean values and confidence intervals (at a 95% confidence level) for 30 runs in each scenario. Due to the normality characteristics of the data under consideration, we apply the ANOVA (ANalysis Of VAriance) parametric statistical test together with its post hoc follow-up analysis over the independent groups considered. The ANOVA statistical test returns a p-value > 0.05 indicating (with 95% of confidence) that there are no statistical differences among the groups and a p-value < 0.05 if there is at least one pair of groups with a statistically significant difference. The intervals shown in the graphs for the post hoc analysis are computed in such a way that (to a close approximation)

the two configurations compared are significantly different if their intervals are disjoint and are not significantly different if their intervals overlap. In our case, the delivery ratio interval associated with each group is represented by a horizontal line (with a circle representing its mean value). For each graph, we choose one group for emphasis (represented by a black horizontal line and delimited by two vertical dashed lines).

Setting the Metrics of CGrAnt

This section investigates how selected metrics and ACO operators can improve the communication among swarms in the population space and thus, assist in obtaining better solutions. Sections 5.1 and 5.2 analyze the influence of certain metrics associated with the ACO operators of CGrAnt. Section 5.3

analyzes the influence of selected metrics in characterizing the utility of each node (solution) as a message forwarder.

Heuristic Function

We for n after a complete path has been found (which includes n), and n has received the visit of a BA (as seen in Section 3.5). ( 4) In highly connected scenarios where the set of global solutions is always available and the same solution can be frequently selected, the percentage of available resources (e.g., the buffer) may be an important metric to consider; nevertheless, in an environment where the contacts are sparse (as in the DTNs), information on the social proximity between two nodes seems more important.

Pheromone Concentration

In Figure 5 presents the post hoc analysis of ANOVA highlighting the best composition (4). As depicted, there is no overlap among the intervals. This behavior verifies that the use of both local and global information (heuristic function and pheromone concentration) along with the RD i,m metric achieves higher performance.

CGrAnt Component Analysis

The influence of the CGrAnt's components on the message delivery ratio and message redundancy ratio are evaluated for the PoI and WD scenarios.

The message redundancy ratio is expressed as Redundancy = (B transm -B delivery )/B delivery , in which B transm represents the number of bytes trans-mitted to nodes, and B delivery , which is the number of bytes delivered to their destination.

Initially, an additive methodology is adopted in which components are added one by one to the previous protocol configuration until its final version (configuration 6) is reached (see Table 3). The first two configurations represent the CGrAnt protocol that considers only the ACO metaheuristic. The pheromone concentration slightly increases the delivery ratio and reduces the number of replicated messages. The influence of the new components incorporated into CGrAnt (i.e., CA's belief space) is analyzed for configurations 3 to 6.

When comparing the results obtained from the pure ACO metaheuristic (configuration 2) with the final performance of CGrAnt (configuration 6), the following gains are achieved:

• in the POI scenario, the configuration 2 obtains 48.61% against 58.93% of message delivery in the configuration 6. This represents a percentage increase of message delivery in 21.23%;

• in the WD scenario, the configuration 2 obtains 54.97% against 63.19% of message delivery in the configuration 6. This represents a percentage increase of message delivery in 14.95%;

• in the POI scenario, the configuration 2 obtains 15.97% against 10.37% of message redundancy in the configuration 6. This represents a percentage decrease of message redundancy in 35.07%;

• in the WD scenario, the configuration 2 obtains 68.62% against 12.43% of message delivery in the configuration 6. This represents a percentage decrease of message redundancy in 81.86%.

The Situational knowledge (configuration 4) aims to dynamically restrict the number of FAs (and, consequently, the number of messages replicated) to only the most promising forwarders. The History knowledge (configuration 5)

provides the exploitation of already known good solutions and consequently increases the message delivery ratio. The Domain knowledge 1 (configuration 3) privileges the exploration of the search space and the Domain knowledge 2 (configuration 6) favors the exploitation. According to the analysis of configurations 3 and 6, the Domain knowledge aims to increase the message delivery and reduce the redundancy ratio.

GrAnt, our previous ACO-based protocol presented in (Vendramin et al., 2012b), performs better than CGrAnt in PoI (i.e., GrAnt provides 62.10 ± 0.2% of message delivery and 7.05±0.1 of message redundancy). However, for the WD scenario, CGrAnt outperforms GrAnt (the latter achieved 60.25 ± 0.75% for delivery and 13.65 ± 0.14 for redundancy). CGrAnt presents better performance in WD rather than in POI scenario because of the Domain Knowledge. The Domain Knowledge considers the node mobility in order to determinate if a node is a good message forwarder and, consequently, if that node must exploit or explore the search space. In WD there are several mobility patterns, i.e., buses and vagabonds nodes with high mobility.

Otherwise, in POI, the mobility of nodes is very similar and the information of the Domain knowledge is less relevant.

Additionally, CGrAnt has the advantage of modeling at a higher abstraction level that enables the elimination of any knowledge of the CA belief space in a simple way (e.g., the history knowledge can be eliminated when the environment is more connected and fewer messages need to be forwarded).

Table 4 represents the eliminatory analysis of the CA's belief space proposed by CGrAnt. The first configuration in Table 4 represents the CGrAnt protocol including all components. In analyzing this table we conclude the following:

• Domain Knowledge aims to increase the message delivery ratio and reduces the message replication. This is particularly true in the WD scenario in which the nodes generally have a stagnation degree (SD n ) lower than the average stagnation of its social network (SD J ), and consequently, the Domain knowledge has greater influence. Without this knowledge, the message delivery ratio is reduced by 1.77% (PoI) and 1.40% (WD) and the message redundancy ratio increased by 0.77% (PoI) and 92.27% (WD);

• Situational Knowledge aims to dynamically restrict the FAs to only good forwarders, and its influence on the message redundancy ratio is therefore greater. Without this knowledge influence, we observe an increase of 51.78% (PoI) and 248.51% (WD) in the message redundancy ratio and a reduction in the message delivery ratio of 9.15% (PoI). In the WD scenario we have an increase of message delivery ratio of 1.65%;

• History Knowledge aims to enhance already known good solutions and thus increases the message delivery ratio. Without the influence of this knowledge, there is a reduction of 3.78% (PoI) and 3.4% (WD) in the message delivery ratio with a lowest cost incurred in the replication of messages -33.85% (PoI) and -12.55% (WD).

It may be noted that the use of the multiple knowledge incorporated in CGrAnt improves its final performance. As the use of multiple techniques in ensemble systems, the combination of a set of techniques on an suitable consensus function provides better performance than each individual technique.

The CGrAnt Overall Performance

This section investigates how CGrAnt performs as a forwarding protocol when compared with the Epidemic and PROPHET protocols under varying networking parameters. We performed 30 runs, and the reported results represent the mean and confidence intervals (at a 95% confidence level) values.

To evaluate the reliability and the cost of the three protocols, we considered the following three performance metrics: (1) message delivery ratio, (2) message redundancy ratio, and (3) average message delivery delay. The performance of the three DTN protocols with variations in the buffer sizes and message TTLs in the WD scenario is presented in (Vendramin et al., 2012a). The results in (Vendramin et al., 2012a) show that CGrAnt achieves a higher message delivery ratio and a lower redundancy ratio than those of Epidemic and PROPHET.

Analysis of Different Buffer Sizes

Analysis of Different Simulation Times

We also perform an experiment to evaluate the number of messages delivered by the three protocols along the simulation time in the PoI (4MB of buffer size and message TTL of 600) and the WD scenarios (10MB of buffer size and message TTL of 1, 800), both with a communication range of 10m.

The aim in this section is to demonstrate that a better delivery ratio can be achieved as the time increases.

Figure 8 shows the message delivery ratio obtained by the three protocols over time in the PoI and WD scenarios with a 10 m range. In CGrAnt, the performance gain is greater mainly in the WD scenario. When the simulation time is increased from 400,000 to 2,800,000 seconds, CGrAnt delivers slightly better performance via an increase of 7.37% (PoI) and 17.45% (WD) in the message delivery ratio. This gain is justified by the fact that the more is the gathered information by CGrAnt over time, the better are the choices it can make concerning message forwarding candidates. In contrast, PROPHET and Epidemic did not exhibit any significant variation of performance when the simulation time was increased.

Analysis of Operation Costs

Another important consideration in protocol performance is the cost of initializing/updating and storing the state of the network and nodes. This cost covers the amount of the following types of information: (1) locally exchanged between every two nodes i and j during any contact opportunity, and (2) locally stored in each node i of the network. For this analysis, we considered the PoI scenario with the emphasized parameters presented in Table 2.

For the storage cost in terms of the total number of bytes exchanged between nodes i and j during every contact opportunity, PROPHET displays a higher cost due to the exchange of its delivery predictability list. Due to the transitive property of PROPHET, the number of records in the predictability list of a node rapidly reaches the total number of network nodes (139, excluding itself). Thus, the number of bytes exchanged in both directions of the contact is 2,224 bytes (139 × 16 bytes), as it is shown in Table 5.

For the CGrAnt protocol, during the message forwarding phase, 16 bytes are sent by i to its neighboring node j, identifying a data message m to be sent and the stagnation degree of i. At the same time, 29 bytes are sent by j to i representing node j on how well it can perform as a forwarder for m: including its stagnation degree, its degree centrality, its social proximity with the destination d of the message m stored in node i, its betweenness utility relative to d, and an indication (true or false) that it knows that m was already received by d.

For the cost in terms of the total number of bytes stored in each node i, because Epidemic relies on the message replications to eventually deliver its messages, its storage cost is null (i.e., it is a stateless protocol

Figure 1 :

 1 Figure 1: Operation Modes of the CGrAnt Protocol.

Figure 2 :

 2 Figure 2: Belief Space of a Node.

  which measures the quality of a path p constructed by an FA k between nodes s m and d m . It encompasses the number of hops (|p|) and the average degree centrality of nodes n (DC n )

  U n,d (t) can thus consider only local or both local and global information. The local information η n,d (t) is the heuristic function of ACO measured by SP n,d , and the global information τ (i,y),d (t) is the pheromone concentration on each link (i, y) belonging to a path to d, and y is defined as:

  3.3.1. Domain Knowledge introduced to support the analysis of local and specific DTN dynamics. Domain knowledge keeps CGrAnt updated on the relative local dynamics of each node i, which is evaluated in this paper based on the relationship between SD i and SD i J . The knowledge is distributed among nodes, Dom i , for i = 1, ..., N , where N is the number of nodes available in the network and Dom i assists CGrAnt in characterizing i into three classes: a node with high, medium or low stagnation degree. Based on this information and the specific heuristics of a DTN forwarding problem, the Domain knowledge can set the status of the path search (i.e., exploration or exploitation). The Acceptance and Update functions of the Domain knowledge occur more frequently than its Influence Function because they are called during the node encounters. The Influence Function acts only during the message forwarding phase.

  Update and Influence functions are called. The new solution thus replaces the previous solution (best f wd m = j), and the new solution quality (U j,d ) updates U best f wdm,d (i.e., U best f wdm,d = U j,d ). The Influence Function creates a new FA and forwards it along with m to the new solution j. The Influence function thus dictates the future of each path built for a pair s m -d m and the number of generated ants.In the following sections, we describe in more detail the two phases that dictate the main functioning of the GrAnt routing protocol: (1) Message Forwarding or Path Search, which is represented by FAs looking for a set of paths and the updating of selected knowledge and metrics. In this phase occurs the data message forwarding; and (2) Backward, which is represented by BAs updating the knowledge and metrics stored in the nodes.

  the exploration stops (line 16)), or (ii) i is an intermediate node with a low stagnation degree (because i is a highly mobile node, it does not forward m, thus, both exploration and exploitation are stopped (lines 19 and 20)).Aside from Domain knowledge, the History and Situational knowledge also influence the CGrAnt message forwarding. The History knowledge influences the forwarding (line 33) when the decision is to exploit the solutions already found: i forwards m to a solution j if node j's betweenness utility (BU j,d ) is higher than the betweenness utility of node i's social network(BU i J,d stored in His i,d , as observed in line 47). The Situational knowledge influences CGrAnt (line 44) when the decision is to explore the network or when better solutions appear. Node i only forwards m to a new solution j if one of the following two conditions is satisfied: (i) The utility of j (U j,d ) is higher than the utility of the best forwarder previously found for m (U best f wdm,d , which is stored in Sit i,m , as observed in lines 53 and 54). This condition attempts to locate a new best forwarder for m among the current neighboring nodes of i; (ii) At the beginning of the exploration (i.e., m was not forwarded to any other node and best f wd m = i and U j,d = U i,d , as in lines 26-27, 36-38). The Situational and History knowledge are important contributions of CGrAnt because they dynamically control the number of created ants and the data message redundancy by setting each new best message forwarder or forwarding m to already known good nodes, thus differing from the pure ACO algorithms proposed for DTNs.

  Dom i . The search for new paths toward d m continues until i performs one of the following actions: (1) encounters d m , (2) becomes aware of the successful delivery of the corresponding data message to d m , or (3) detects that the Time to Live (TTL) field of the data message has expired. Throughout its path search, an FA carries the following information: the ID of s m , the ID of d m , the node IDs through which it passes (between s m and d m ), and the degree centrality of each visited node j (DC j ). The individual qualities update the partial quality of the path under construction by the FA.

(

  due to connection partitions), the message forwarding phase of the CGrAnt protocol is guided by a local path search provided by the heuristic function information. Differing from other protocols that use only global (pheromone concentration) or local (heuristic function) information, CGrAnt contains additional flexibility, because the decision is based on all available information (both ACO operators and knowledge stored in the CA belief space).

  offices, and roads. The area is divided into four regions denoted by R A to R D . Eight groups of nodes, denoted by A to H, are created to represent the node movements into specific regions. Groups A to D simulate only intraregion movements (e.g., group A simulates the node movements into region R A ). Groups E, F , and G simulate node movements between R A and other regions, and H simulates movements among all regions. The assignment of nodes per group is as follows: A has 258 nodes, B has 119, C has 154, D has 154, E has 102 (i.e., E = A ∩ B), F has 122 (i.e., F = A ∩ C), G has 122 (i.e., G = A ∩ D), and H has 70 (i.e., H = A ∩ B ∩ C ∩ D). The WD movement model represents an activity-based environment that simulates the daily lives (activities) of people who go to work in the morning, spend the day working, may go to a public place for leisure activities with friends at the end of day, and return to their houses at night. In WD, the total area (10, 000 × 8, 000 m 2 ) encompasses meeting points, buses, houses, offices, and roads. The area is divided into four regions denoted by R A to R D . Eight groups of nodes, denoted by A to H, are created to represent the node movements into specific regions. Groups A to D simulate only intraregion movements (e.g., group A simulates the node movements into region R A ). Groups E, F , and G simulate node movements between R A and other regions, and H simulates movements among all regions. The assignment of nodes per group is as follows: A has 258 nodes, B has 119, C has 154, D has 154, E has 102 (i.e., E = A ∩ B), F has 122 (i.e., F = A ∩ C), G has 122 (i.e., G = A ∩ D), and H has 70 (i.e., H = A ∩ B ∩ C ∩ D).

  first analyze different sources of information in the ACO local operator or Heuristic Function (η n,d (t)). Recall that a node n is selected from a set of candidates to forward a message m to its destination d. In this section, the CGrAnt performance is evaluated by considering each of the following metrics associated with η n,d (t): (1) SP n,d , (2) DC n , (3) BU n,d , and (4) F B n , which represents the free space available in the buffer of a node n.The experimental results show that when CGrAnt uses the SP n,d metric, it delivers more messages (58.93 ± 0.19%) than the DC n (47.21 ± 0.17%), the BU n,d (53.92 ± 0.17%), or the F B n (49.72 ± 0.28%).

Figure 3

 3 Figure 3 presents the post hoc analysis of ANOVA highlighting the SP n,d metric. The SP n,d metric guarantees the highest message delivery ratio. This associated to the fact that there are no overlaps among the intervals resulted from other metrics, lead us to conclude that SP n,d provides better performance than the other metrics. The main reasons for the better performance of the SP n,d metric are listed as follows: (1) SP n,d indicates the proximity of n relative to d because it provides an estimation of the probability of future encounters between n and d. Moreover, SP n,d contains information available along all of the search process. (2) DC n indicates the popularity of n relative to all other nodes in the network instead of specific information for the candidate forwarder and d, as in SP n,d . (3) BU n,d provides important information for the nodes that successfully intermediated a communication to d; however, it is only available

Figure 3 :

 3 Figure 3: ANOVA results to Heuristic Function.

  this work, the pheromone concentration in the ACO global operator is associated with the quality of a complete path constructed by an ant k between the s m and d m nodes (i.e., τ k (i,y),d (t) = Q p k sm,dm (t)). Next, after defining the Heuristic function, we evaluate which type of information have more influence on Q p k sm,dm (t). The CGrAnt performance is evaluated using different metrics to predict the path quality: (1) the average Degree Centrality (DC) of nodes n belonging to the path along with the reciprocal of the existing number of hops (|p|) in the constructed path, i.e., as in Eq. 1; (2) only the second term of Eq. 1; (3) only the first term of Eq. 1; and (4) the average Betweenness Utility of node n relative to d (i.e., Q p k sm,dm (t) = n BU n,d |p| ). The simulation results show that when using a composite metric encompassing DC and |p|, CGrAnt delivers more messages (58.93 ± 0, 19%) than when it uses only the basic metrics |p| (51.11 ± 0.22%), DC (51.10 ± 0.21%), and BU (49.89 ± 0.22%).

Figure 4

 4 Figure4presents the post hoc analysis of ANOVA highlighting the composite metric (DC and |p|). As shown, the composite metric provides the best message delivery ratio. In addition, because there are no overlaps among the intervals of other metrics, we conclude that the composite metric provides better performance than the basic metrics. This result indicates that the node popularity is a good indicator of the node's ability to forward messages. This is particularly true in scenarios with intermittent connections, as in DTNs. Moreover, the importance of |p| is due to the fact that the smaller is the path, the fewer are the network resources consumed and the less is the communication interference that occurs.

Figure 4 :

 4 Figure 4: ANOVA results to Pheromone Concentration.

Figure 5 :

 5 Figure 5: ANOVA results to Node's Utility Analysis.

Figure 6

 6 Figure 6 depicts the performance of the three protocols with variation of the buffer sizes (from 4 MB to 16 MB) for the PoI scenario. The dashed curves with empty points denotes the results for nodes that operate at a communication range of 10 m and a transmission rate of 2 Mbps (representing bluetooth devices). The solid curves with black points show the

Figure 8 :

 8 Figure 6: Protocols' performance over different buffer sizes -PoI scenario.

,

  His i,2 (t), ..., His i,D i (t)}, where D i ≤ N represents the number of destination nodes for which node i originated or intermediated a path.The Acceptance and Update Functions of the History knowledge are called in the backward phase, and its Influence Function acts in the message forwarding phase.The Acceptance Function is called after node i receives a BA from a neighboring node (j or d), indicating that a complete path to d has just been found. The betweenness utility of i with respect to d (BU i,d ) is always accepted to update the belief space of i. The betweenness utility of the neighboring node j (BU j,d ) is also accepted to update the belief space of i if and only if the BA did not come from d. After the acceptance phase, the Update Function is called to calculate BU i J,d .

The BU j,d and BU i J,d dynamics are considered by the Influence Function when evaluating the improvement directions of each neighboring node j as a candidate forwarder for message m to d: dr j = +1, if BU j,d > BU i J,d ;

  Sit i,m . The acceptance condition can be relaxed to accept nodes with the same utility of the best forwarder if the corresponding search status exploration is true. Only one solution is accepted in each update. After accepting a new solution, the

The Acceptance, Update, and Influence functions of the Situational knowledge are called during the message forwarding phase.

The Acceptance Function operates with the understanding that if a new neighboring node j (partial solution) is found, it is accepted to update the belief space of i only if U j,d > U best f wdm,d , where U best f wdm,d is the current best forwarder utility for m stored in the sub-knowledge

Table 1 :

 1 Myriam Regattieri Delgado received her graduate degree at Electrical Engineering from UFG in 1990 and Ph.D. degree in Computer Engineering from UNICAMP in 2002. Currently, she is associate professor at UTFPR. Her research interests include natural computing, swarm intelligence applied in computer networks. Aline Carneiro Viana is a Researcher at INRIA Saclay. She got her Ph.D. in Computer Science from the University Pierre et Marie Curie in 2005. After holding a postdoctoral position at IRISA/INRIA Rennes, she joined INRIA Saclay in 2006. Her research is primarily in success data delivery in wireless self-organized and adaptive networks. Mauro Fonseca received the B.Sc Degree in Computers Engineering from the PUCPR in 1994 the Ph.D. degree in Computer Networks from University Pierre et Marie Curie in 2003. He is currently an associate professor at UTFPR. His research interests include wireless networks and network performance. Summary of the metrics and variables used to describe the network and CGrAnt , j or d in a link toward d N The total number of nodes available in the network M The total number of data messages to be forwarded J Set of nodes j encountered by the node i (social network of i) D i The total number of destination nodes for which i originated or intermediated a path CGrAnt Variables F A/BA A general Forward/Backward Ant k A specific FA/BA Km The total number of FAs generated for a message m p A complete path with a total of |p| hops Pm Group of paths p constructed by ants for a message m W Event window drn Improvement direction of a node n V i /Vs Inferior/Superior limits which define the range of medium stagnation degree CGrAnt Local Metrics F E n,d Frequency of Encounters between n and d DE n,d Duration of an Encounter between n and d P T n Average Pause Time in the places visited by a node n M Sn Average Movement Speed of a node n DCn Degree Centrality of a node n RD i,m Relationship Degree of a node i with respect to a specific buffered data message m CGrAnt Global Metrics |p| Number of hops in a complete path p BU n,d Betweenness Utility of a node n in relation to d Betweenness Utility of the social network of i in relation to a destination d SP n,d Social Proximity between nodes n and d U n,d Utility of a node n as a message forwarder to d η n,d Heuristic Function measured by SP n,d τ (i,y),d Pheromone concentration on each link (i, y) belonging to a path to node d SDn Stagnation Degree of a node n SD i

	). Although

in the total number of bytes generated in the network. Similarly, when compared with PROPHET, these reductions are 34.86 ± 0, 18% (PoI with 10 m), 43.37 ± 0, 15% (PoI with 100 m), 74.59 ± 0, 34% (WD with 10 m), and 78.57 ± 0, 56% (WD with 100 m) in total bytes generated in the network.

Therefore, we conclude that with the smallest generated overhead, CGrAnt is able to choose the best message forwarders and reduce the total number of data bytes replicated in the network.

J

  Stagnation Degree of the social network of node i Q p k sm,dm Quality of a path p (from sm to dm) constructed by FA k History Knowledge of i with respect to d Sit i,mSituational Knowledge of i with respect to m

		CGrAnt Knowledge
	Dom i	Domain Knowledge of node i
	His i,d

Table 2 :

 2 Simulation parameters.

Acknowledgements

This work is partially supported (1) by the Brazilian National Research Council (CNPq), under research grants 309571/2014-6 to A. Munaretto and 309197/2014-7 to M.R. Delgado, and 479159/2013-0 to A. Munaretto and

(2) by the STIC AmSud UCOOL project.

Algorithm 1 Pseudo-code of the CGrAnt Message Forwarding.

1: Algorithm Initialization 2: for each message m in the buffer of node i do 3: best f wdm ← ∅; {No forwarder is assigned to m} 4: end for 5: {BU , Pheromone concentration, and History knowledge are updated during the backward phase} 6: for each message m in the buffer of node i do 7: U i,d ← U n,d ; {Updating node i utility, as in Eq. 2} 8: if (best f wdm = ∅) then 9:

best f wdm, d ← i {Initializing the Situational Knowledge}; 10: 21: end if 22: -------------------------23: Message Forwarding 24: for all connections j do 25:


R Ferraro

S Danzeca

M Brucoli

A Masi

M Brugger

L Dilillo

Design Of A Radiation Tolerant System For Total Ionizing Dose Monitoring Using Floating Gate And Radfet Dosimeters

1. Abstract 3. TID Monitoring procedure 4. Radiation Assurance

Conclusions

The Total Ionizing Dose Monitor (TIDMon) is a radiation tolerant system designed to measure the effect of the TID on a new prototype of Floating Gate Dosimeter (FGDOS) and compare it against the Radiation-sensing Field Effect Transistors (RadFETs) dosimeter.

In this work we present the design strategy adopted for the control of the sensors and the architecture, the radiation reliability and the performance achieved by the system. Four IP cores constitute the generic tester part :

• The CoreABC, an assembler-based configurable softcore provided by MicroSemi which is the master of the system. The core contains in assembly-based language the reading routine of the sensors. • The CoreAPB, an APB interface to connect the slave IP cores to the CoreABC.

• The CoreUART, a configurable APB serial controller provided by MicroSemi.

• The ADC Controller which provides the measurements of the analogue values of the sensors and the reference values of the board. Two IP cores are dedicated to the sensors :

• The FGDOS Controller performs the measurement of the frequencies and manages up to four FGDOS. • The RadFETs Controller performs the reading procedure for up to two RadFETs.

 The TIDMon allows us to finely characterize and find the best conditioning to use the FGDOS with the maximum of performance as a TID sensor for CERN dosimetry purposes.  The tester architecture proved to be robust against various harsh radioactive environments and can operate up to 30 krad(SI).  The next step to consider for the Tester architecture will be to extend the lifetime of the architecture actually limited by the increase of the ADC current consumption as a result of the accumulated dose.  The performances and the modularity of the test architecture provides us a quick and robust, ready-to-use test system able for other CERN radiation testing activities.

• Reading Step : The gate and drain are shorted to the ground, and the sensor is supplied by a current source for a period of 100 ms. • Biasing Step : The drain, source and gate pins are shorted to the ground. The gate can be biased to 5V in order to increase the sensibility.

Results

 A Triple Modular Redundancy (TMR) mitigation technique is applied on the FPGA IP cores at the register level by means of a commercial synthesis tool and at the memory level manually.  The board is entirely based on COTS components tested against radiation effects :

• SEEs and TID: 230 MeV protons (up to ) • Displacement damage: 1 MeV neutrons (up to ) • TID:

source up to 50 krad(Si) TID

Design Choices

 In the nominal configuration of the FGDOS with a sampling of 1 Hz, the TIDMon is able to charge the sensors in less than 1 sample, thus the blind time is reduced to the minimum.  The TIDMon can achieve a measuring accuracy of 16 mrad(SI).

 The board worked without issues during the several test campaigns performed at CHARM mixed-field facility or with irradiation.

• The frequency meter process used two sub-processes :

• A precise one that calculates the frequency in 1s with an accuracy of 1 Hz.

• A fast one that calculates the frequency in 15ms with an accuracy of 128 Hz. • The charge process recharges automatically the sensor to a desired value when it is discharged below a defined threshold. These two values are configurable online.

• The SPI interface allows to :

• Set the radiation sensitivity (High / Low)

• Read the internal temperature sensor • Bypass the VCO, to have on the output the current of the reading MosFET of the floating gate.

The TIDMon measures every second the TID sensors and also the voltage regulators and the current source of the board in order to monitor the level of degradation of the tester. Current source 10µA

4.9 15

Two parts compose the system :

• The tester part which is a generic radiation tolerant architecture able to acquire mixed-signals from the DUT and perform complex data processing. • The DUTs part that contains the dosimeters sensors and the circuitry needed to manage them.

Figure 3 -

 3 Figure 3 -Functional operation of FGDOS during irradiation, the output of the sensor is provides by an embedded Voltage Controlled Oscillator (VCO) that convert the gate potential in a square wave signal.

Figure 1 -Figure 2 -

 12 Figure 1 -TIDMon board and general hardware architecture with on the right the Tester part and on the left the DUTs part

Figure 7 -

 7 Figure 7 -FGDOS measurement perform during a radiation test campaign and the corresponding processed dose.

Figure 6 -

 6 Figure 6 -RadFET Dosimeter reading procedure and circuit with ADC Gains which allows the exploitation of the full range of the sensors.Time Time