POSOP Routing Algorithm: A DTN Routing Scheme for Information Connectivity of Health Centres in Hilly State of North India

Abstract

We explore the application of partitioned network for providing health services in difficult terrain where fixed communication infrastructure is not cost-effective due to low population density and very high cost of setting up a permanent infrastructure. We propose a hybrid routing which is persistent, on-demand, scheduled, opportunistic, and predicted (POSOP) routing algorithm, that exploits various types of contacts existing in a partitioned, hybrid, and sparse network. Such networks may be used to provide guidance from specialist doctors to junior doctors working in primary health centres. We present a scenario from Uttarakhand (a state in hilly region of North India), where POSOP routing algorithm may be used to provide improved health services. Using simulations, we evaluate the performance of POSOP routing algorithm on three metrics, messages delivered, average delay suffered by the delivered messages, and average message traffic. We compare the performance of POSOP routing algorithm with two routing schemes, namely, epidemic and spray and wait on the three metrics. Our approach outperforms both the routing schemes.

1. Introduction

The fixed infrastructure for communication is not possible in hilly regions such as Uttarakhand (a state in the Republic of India) because of frequent landslides and natural disasters. Also, due to physical barriers and lack of economic feasibility, the existence of permanent communication infrastructure is not sustainable in these types of regions. Delay/disruption tolerant network (DTN) may prove to be a feasible solution to provide connectivity to people residing in such topographical terrain. DTNs are partitioned networks with intermittent connectivity between the nodes. Since end-to-end path may not exist between the nodes, messages have to be stored, carried, and forwarded to the destination by relay nodes. Delay is inevitable in such networks.

Request for comments (RFC) of DTN [1] describes five types of contacts, namely, persistent, on-demand, intermittent-scheduled, intermittent-opportunistic, and intermittent-predicted, that may exist in DTN. Routing schemes [2–15] exploit one or two such types of contacts to route the messages. To the best of our knowledge, none of the routing schemes proposed in literature exploits all the five types of contacts.

In this paper, we present POSOP routing algorithm, a hybrid routing scheme that exploits all five types of contacts to route the messages. First, we have depicted the problem scenario that may contain all five types of contacts. Then, we have presented an algorithm of the proposed routing scheme that exploits various contacts and chooses the type of contact according to the message type. We have presented the applicability of the proposed routing approach for providing the information connectivity to health care centres located in rural hilly villages of Uttarakhand with district hospitals existing in major districts and super speciality hospital situated in the state capital.

The paper is organized as follows. Section 2 presents the motivation for doing the research work. Section 3 presents the related work. Section 4 presents problem scenario and the proposed solution. Section 5 presents the applicability of DTN contacts in the proposed solution. Section 6 describes the POSOP routing algorithm. Section 7 presents the experimental setup and simulation results and Section 8 presents the conclusions and future work.

2. Motivation

The hilly state of Uttarakhand, India, is a state with sparse population scattered over a large area. The status of health centres in remote villages of Uttarakhand is not very sound as specialist doctors mostly resist the transfers to the difficult terrain. In the physical absence of specialist doctors, their advice, communicated over telecommunication network, might prove to be very helpful in providing better health facilities. To worsen the situation further, thin population in the area and frequent landslides, especially during rainy season, make setting up and maintenance of permanent and fixed infrastructure economically less feasible. The infrastructureless setup such as MANET formed by smart hand held devices might not be very effective in the given scenario because the population is very thin and spreads over a large area and therefore overlapping regions of mobile devices are rare. Due to only intermittent connectivity, routing of messages in such networks is a challenge. The recent incident (June 2013) of flash floods in the region that took away the life of thousands of people became the motivating factor for undertaking the study of application of DTN for providing health services to such hilly terrains and disaster hit areas.

3. Related Work

Epidemic routing [12] is one of the earliest approaches proposed for DTN. This approach exploits opportunistic contacts to deliver the messages. The approach results in high message delivery ratio but also generates huge message traffic. The approach is not suitable where buffer space, processing power, and battery level of relay node are constrained.

The problem of message traffic was overcome by using probabilistic approaches and controlled flooding [9]. Both epidemic and probabilistic techniques exploit only opportunistic contacts for message forwarding. Social groups based routing schemes [2, 5, 6, 16] use the mobility pattern of nodes for choosing the best opportunistic contacts.

An approach proposed by Jain et al. [7] exploits contact history for predicting the futuristic contact information of the node and chooses the shortest path for routing the messages. The success of this approach is based on existence and correctness of nodes mobility data.

Some of the routing approaches have exploited the idea of scheduled movement of special nodes such as ferry and data mules [11, 15]. The approach is able to utilize the existence of the availability of scheduled contact only. DSG-PC [8], a routing approach, exploits both the opportunistic and scheduled contacts for routing the messages. In this approach, a node decides whether to forward a message using opportunistic contact or wait for an arrival of a scheduled contact on the basis of message ttl (time to live). Scheduled carrier has been shown to add a delay as it follows a fixed path and contacts a node at a fixed time.

The wireless network has been shown to be an effective but challenging communication mechanism in rural areas. In [17], the authors present two projects in India in which they have used IEEE 802.11 (WiFi) as a cost-effective technology to provide wireless access to rural areas: (1) Digital Gangetic Plains (DGP) project was initiated in 2002 at the Indian Institute of Technology, Kanpur (IITK), Uttar Pradesh, and (2) Ashwini project was a network deployment effort by the Byrraju Foundation, to provide broadband access and services to a group of villages in the West Godavari District of Andhra Pradesh, India.

In [18], authors presented that providing connectivity to underserviced and inaccessible rural areas comes with a unique set of challenges such as the high cost of establishing infrastructure like installing equipment, lack of reliable power, skill shortages, and high cost of providing Internet connectivity which is mostly satellite based. The authors studied the deployment of low-cost wireless rural networks in South Africa and Zambia and demonstrated very encouraging results.

4. Problem Scenario and Proposed Solution

Uttarakhand is a state in the Republic of India. The state is situated in the foothills of the Himalayan range, with most of the villages situated in hilly area. Total area of Uttarakhand is 51,125 sq km and population density of Uttarakhand is 189 per sq km which is lower than the national average of 382 per sq km [19]. There are two divisions, namely, Kumaon region and Garhwal region comprising 13 districts and 15828 villages/towns in the state [20]. Currently, the state capital has a super speciality hospital (SSH) and there are about 12 district level hospitals (DLHs). There are about 322 state allopathic hospitals (SAH) located in villages. Due to shortage of trained medical staff at SAH, people living in remote villages depend heavily on DLH. As the state has poor physical connectivity between various rural and urban areas, which further deteriorates during monsoon due to flash floods, mild tremors, and landslides, the state administration has provided mobile medical units (MMUs). MMUs provide periodical, accessible primary health care services to rural people. The SSH and DLHs are persistently connected for information exchange with wired networks. But there is poor connectivity between DLH and the 322 SAH in semiurban and remote villages. Due to physical barriers and lack of economic feasibility, the existence of permanent communication infrastructure is not sustainable. DTN may prove to be a feasible solution for providing information connectivity in this region as shown in Figure 1.

Figure 1

Message transmission between health centres using POSOP routing algorithm in Uttarakhand.

We propose to connect each of the SAH or primary health centres (PHC) with DLHs, for information exchange, using DTN. The smart phones carried by people can be used as relay nodes for providing opportunistic/predicted contacts. Apart from opportunistic contacts, nodes can be mounted and set up on ambulances which can act as on-demand contacts and MMUs can provide scheduled periodic contacts. The SSH and DLHs already have persistent connectivity.

The message generated at the SAH or PHC may be carried either through mobile devices, set up on ambulances or MMUs, or by human carriers. The message destined for DLH or SSH may be delivered to any of DLH or SSH. With persistent connectivity between DLHs and SSH, the message will reach its destination. In the given problem scenario, the message source and message destination are stationary. A message is forwarded to its destination through relay nodes. Since information exchange between SAH/PHC and DLH/SSH may contain health related information, we have categorised the messages based on two parameters: priority and time to live (ttl). We have assumed that a message generated by SAH/PHC and DLH/SSH may be of high or low priority. Also, a message may have a small or large value of ttl. The categorisation of the message as low or high priority or small or large ttl depends upon the type of disease/ailment with respect to which message is generated. Table 1 shows a list of some of the diseases and their message category. There are four types of messages, that is, high priority and small ttl, high priority and large ttl, low priority and large ttl, and low priority and small ttl. The messages are categorised as expedited (high priority and small ttl), normal (high priority and large ttl, low priority and small ttl), and bulk (low priority and large ttl) [21]. In this paper, we present a hybrid routing approach that exploits the existence of all the 5 types of contacts existing in a network and provides an efficient message routing mechanism. Depending upon the category of message (expedited, normal, and bulk), it may be routed through one or more contacts. Also, a message may or may not be replicated depending upon its category.

Table 1

List of diseases and their message categories.

S. number	Type of disease/ailment	Message category
1	Emergency and accidental cases	High priority and low ttl
2	Planned surgery and delivery cases	High priority and high ttl
3	Seasonal disease	Low priority but small ttl
4	Replenishment of inventory	Low priority and low ttl

5. Applicability of DTN Contacts in the Proposed Solution

When a patient arrives at a PHC/SAH and doctors need to consult a specialist at DLH/SSH, they generate a message containing complete health details of the patient. Similarly, an advice given by a super specialist consultant is a message generated by DLH/SSH for a doctor attending patients at DLH/PHC. All these messages, destined to PHC/SAH or DLH/SSH, are forwarded through one or more relay nodes that deliver the message to its destination.

5.1. Description of Contacts

5.1.1. Opportunistic Contact

Villagers, carrying mobile phones with preconfigured DTN application, going to urban regions (cities and towns) may act as message carriers. When they come in contact with PHC/SAH, messages may be exchanged opportunistically. The message is then carried to a destination by the mobile carrier. Using this approach, a message is forwarded to its destination using two hops.

5.1.2. Scheduled Contact

A MMU visiting a SAH or PHC or DLH/SSH periodically may receive or deliver messages when it comes in contact with the destinations. The time (schedule) at which MMU will visit a health centre is known to these centres. Depending upon the message's ttl and its priority, a message source may choose to forward a message to a scheduled contact. A scheduled contact will also deliver a message to its destination using two hops but with added delay as MMU will take a longer path as it may be covering a number of health centres.

5.1.3. On-Demand Contact

A call to ambulance to provide services during emergency situation provides an on-demand contact in the network. An ambulance may have the capacity to carry one or two patients but the movement of an ambulance from SAH or PHC to DLH/SSH may facilitate the exchange of a large number of messages to/from SAH or PHC to DLH/SSH. During emergency situation where large population is getting affected, frequent to and fro services of ambulance can provide on-demand contact.

The on-demand contact is different from scheduled contact as the latter may cover a large number of health centres before finally delivering a message, whereas on-demand contact will deliver a message following the shortest path and therefore results in minimum delay.

5.1.4. Probabilistic Contact

Some of the people living in rural areas may be working in DLH/SSH. The mobility pattern of such people will make them better capable of delivering messages, in comparison to any other opportunistic contact, to the destination. Such people acting as message carrier represent probabilistic contacts.

5.1.5. Persistent Contact

A backbone network that connects SSH to each of the 12 DLHs provides persistent contact. The contact is extremely useful in situations where specialist doctor at SSH either cannot visit DLH or is situated at one of the 12 DLHs and there is an immediate requirement of medical advice at some other DLH. Moreover, it is easier for people residing in rural area to visit DLH of their district.

6. POSOP Routing Algorithm

We assume that a stationary node (health centre) may generate a message belonging to one of the four categories (see Table 1). When a health centre (stationary node) has a message for another health centre (stationary node), it has to take two decisions: firstly, the number of replicas it should generate for the message and, secondly, whether to forward a message to an encountered node (mobile node) or not. Both the decisions depend upon the type of message generated by a node. Table 2 shows the decision taken by a node when it has a message to be forwarded. In the table, HP and LP mean high and low priority, respectively, and Lttl and Sttl mean large and small ttl.

Table 2

Message types in POSOP routing algorithm.

Msg type	Msg copies	On-demand contact	Opportunistic contact	Scheduled contact	Predicted contact
HPLttl	Single	Yes	No	No	No
HPSttl	Multiple	Yes	Yes	Yes	Yes
LPLttl	Single	No	No	Yes	No
LPSttl	Multiple	No	Yes	Yes	Yes

The POSOP routing approach delivers a message to its destination using two hops. The mobile nodes act as message carriers that receive a message from stationary nodes and finally deliver it to its destination. A message that is of high priority and small ttl is forwarded to all the types of contacts as it has small ttl that may expire soon. A message that is of high priority and large ttl is forwarded through on-demand contact. Only single copy of this message is forwarded. A message that is of low priority and large ttl is forwarded to scheduled contact as it can sustain the delay introduced by scheduled carrier. A message that is of low priority and small ttl is forwarded through all the types of contacts but to reduce the message overhead controlled replicas are generated (see Algorithm 1).

Algorithm 1: POSOP routing.

Notation

   SN-Stationary Node

   MN-Mobile Node

    $$\text{ms}{\text{g}}_{\text{in}}$$ -Incoming Message

    $$\text{ms}{\text{g}}_{\text{out}}$$ -Outgoing Message

Trigger-When SN generates a $$\text{ms}{\text{g}}_{\text{out}}$$

In SN

   rep = 0

   if   $$\text{ms}{\text{g}}_{\text{out}}\in HPLttl$$

   Call On-demand MN

   Forward the $$\text{ms}{\text{g}}_{\text{out}}$$ to MN

   end if

   if   $$\text{ms}{\text{g}}_{\text{out}}\in HPSttl$$

   Call On-demand MN

   Forward the $$\text{ms}{\text{g}}_{\text{out}}$$ to MN

   for each MN that meets SN

     Forward $$\text{ms}{\text{g}}_{\text{out}}$$ to MN

     Receive $$\text{ms}{\text{g}}_{\text{in}}$$ from MN

   end for

   end if

   if   $$\text{ms}{\text{g}}_{\text{out}}\in LPLttl$$

    if SN meets MN and MN is $$ScheduledContact$$

      Forward $$\text{ms}{\text{g}}_{\text{out}}$$ to MN

      Receive $$\text{ms}{\text{g}}_{\text{in}}$$ from MN

    else

      Wait for Scheduled Contact

    end if

   end if

   if   $$\text{ms}{\text{g}}_{\text{out}}\in LPSttl$$

     while rep < 5

      if SN meets MN and MN is predicted

        Forward $$\text{ms}{\text{g}}_{\text{out}}$$ to MN

        Receive $$\text{ms}{\text{g}}_{\text{in}}$$ from MN

        rep++

      else if SN meets MN

        Forward $$\text{ms}{\text{g}}_{\text{out}}$$ to MN

        Receive $$\text{ms}{\text{g}}_{\text{in}}$$ from MN

      end if

     end while

   end if

7. Experimental Setup and Result Analysis

7.1. Experimental Setup

The opportunistic network environment (ONE) simulator [22] implemented in Java and available as open source has been used to evaluate the proposed algorithm. The ONE simulating environment is capable of simulating the mobility pattern of the nodes and the message exchange between them. Many of the routing algorithms applicable to DTN environment are preimplemented in the simulator. We implemented POSOP routing scheme for message forwarding. The map based movement model provided with the ONE simulator was used and the well-known text file (.wkt) files for Uttarakhand region, generated using open street maps [23], were used for simulation. Considering the number of DLHs, SAH, and SSH in the hilly state, we used 335 stationary nodes. Also, considering various places in Uttarakhand to be a tourist destination, we used 50120 mobile nodes. The reason for choosing this number is as follows: the state government run roadways bus service operates 70 buses (approximately) per day, the number of ambulances is assumed to be 50, and we also assumed that almost 50000 (0.5% of the population, population of Uttarakhand is 10 million) people may be carrying mobile devices (smart phones). The parameters used for simulation are given in Table 3. The ttl for expedite messages has been taken as 60–70 min. These expedite messages pertain to medical emergency cases. Although some of the medical emergency cases may require immediate attention (20–30 min), for simulation we used the ttl of 60–70 min. There are two reasons for choosing this ttl. Firstly, on using small ttl, the messages will time out in a short duration. The nodes will drop such messages, although a medical emergency case is capable of handling the delay. Secondly, considering the physical distances and minimum time required to reach from various rural locations to SSH/DLH, the specific value of ttl for expedite messages was chosen.

Table 3

Simulation parameter.

S. number	Parameter	Value
1	Network area	50000 km2
2	Total number of stationary nodes	335
3	Total number of nodes (mobile) providing on-demand, scheduled, opportunistic, and predicted contact	50120
4	Total number of messages generated	3080
4a	Total number of expedite messages	786
4b	Total number of normal messages	1324
4c	Total number of bulk messages	970
5	Buffer capacity of node providing opportunistic and predicted contact	50 MB
6	Buffer capacity of node providing on-demand and scheduled contact	256 MB
7	Buffer capacity of node providing persistent contact	Unlimited
8	The transmission speed of nodes	256 kBps
9	The message (expedite) ttl (time to live)	60–70 min
10	The message (normal) ttl (time to live)	1000–1200 min
11	The message (bulk) ttl (time to live)	2500–2880 min
12	Total simulation time	172800 sec (2 days)

7.2. Result Analysis

We compared the number of messages delivered in epidemic [12] and spray and wait [24] routing to our approach. There are two reasons for choosing these schemes for comparing the results. Firstly, epidemic scheme being most efficient in terms of message delivery may therefore provide good comparison to any new routing approach and, secondly, with ONE simulator the epidemic router is available. The spray and wait routing scheme was chosen for comparison because this scheme delivers a message using two hops. As mentioned earlier, POSOP routing algorithm also delivers a message in two hops. Also, the spray and wait routing scheme is provided with ONE simulator.

The results in Figure 2 show the comparison of expedited messages delivered for the three routing schemes. In POSOP routing algorithm, this category of messages was delivered using all possible contacts whereas in epidemic and spray and wait routing schemes the messages were routed using opportunistic contacts only. Because of using on-demand contact and other types of contacts, the messages (expedited) were delivered with less delay and with high priority resulting in better message delivery ratio. The results clearly show that messages delivered using POSOP approach are substantially higher than those delivered using the other two routing schemes. The normal messages delivered in our approach are also higher in comparison to messages delivered using other routing schemes (see Figure 3). In POSOP routing algorithm, these messages were forwarded using either one type of contacts or multiple contacts depending upon the priority of the message. Both scheduled and on-demand contacts provided very efficient message delivery mechanism and, therefore, POSOP routing algorithm being capable of utilizing the existence of such contacts was better in delivering the messages. The delivery of bulk messages using POSOP approach is comparable to epidemic approach (see Figure 4). In POSOP routing algorithm, bulk messages were forwarded using scheduled contacts and, therefore, a number of messages were in transit when the results were obtained. For epidemic approach this result is slightly better than POSOP routing algorithm because in epidemic approach replicated copies of these messages were forwarded using opportunistic contact.

Figure 2

Comparison of expedite messages delivered in epidemic, spray and wait, and POSOP routing.

Figure 3

Comparison of normal messages delivered in epidemic, spray and wait, and POSOP routing.

Figure 4

Comparison of bulk messages delivered in epidemic, spray and wait, and POSOP routing.

The overall messages delivered and average message traffic generated in POSOP routing algorithm show substantial improvement in comparison to epidemic and spray and wait approaches (see Figures 5 and 6). The controlled message replicas (mostly single copy) and two-hop message forwarding helped the POSOP approach in reducing the message traffic and efficient use of contact helped in reducing the delays.

Figure 5

Comparison of messages delivered for epidemic, spray and wait, and POSOP routing.

Figure 6

Comparison of average message traffic overhead for epidemic, spray and wait, and POSOP routing.

The effect of varying the message ttl on message delivery was also studied (see Figure 7). The message ttl was varied between 10 and 50 min. We observed graceful degradation in case of POSOP routing algorithm for a number of messages delivered with smaller ttl. We also studied the average delay suffered by messages for the three routing schemes. It was observed that POSOP routing algorithm performed better in terms of small delay for all the three types of messages as compared to other routing schemes (see Figures 8, 9, and 10).

Figure 7

Effect of varying the message ttl on message delivery (expedite messages) using POSOP.

Figure 8

Comparison of average delay for expedite messages for epidemic, spray and wait, and POSOP routing.

Figure 9

Comparison of average delay for normal messages for epidemic, spray and wait, and POSOP routing.

Figure 10

Comparison of average delay for bulk messages for epidemic, spray and wait, and POSOP routing.

8. Conclusions and Future Work

The proposed algorithm is a novel approach as it is able to exploit the presence of all the five types of contacts. The POSOP routing algorithm encapsulates the existing routing approaches. Depending upon the type of message, a node has to decide on the routing approach. Through simulations, we showed that performance of the POSOP routing is better than epidemic and spray and wait routing schemes. In the future, we will extend and improve the work by incorporating the constraints specific to the information contents of health domain.