What is STCR

STCR(Social-Tie Content Retrieval)은 k-means clustering algorithm을 사용하여 node간 계층 구조를 만들어 적절한 relay node를 찾는 것이 목적인 routing protocol이다.

STCR의 기본 철학은 "많은 node를 만나는 node가 receiver로 packet을 forward 할 확률이 높다"이다.

현실 세계를 예로 들면 와닿는다. 내가 한정판 CD를 갖고 싶다고 가정하자. 그렇다면 나는 주위 사람들에게 갖고 있는 사람을 찾을 것이다. 그 중 인싸인 친구는 또 다시 주위 사람들 중 한정판 CD를 갖고 있는지 확인을 한다. 상대적으로 아싸인 친구는 한명에게만 확인을 한다.

둘 중 누가 나에게 한정판 CD를 구해 줄 확률이 높을까? 아무래도 주변 사람에 대한 정보가 많은 친구가 구해 줄 확률이 높을 것이다.

STCR은 이러한 철학을 바탕으로 많은 node를 여러 번 만난 node는 높은 계층에 속하고 적게 만난 node는 낮은 계층에 속하게 된다. 이를 통해 packet을 높은 계층에만 forwarding하여 network overhead를 줄일 수 있다는 장점이 생긴다.

---

Preliminary

1. Hello Message Broadcast

• 각 node는 다른 node와 만나기 위해 주기적으로 hello message를 broadcast한다.
• Hello message에는 sender의 node id가 포함된다.

2. Encounter Record

• Sender로부터 hello message를 받으면 receiver는 node id와 timestamp를 저장하고 encounter vector를 생성한다.
• 생성 후 vector는 encounter table에 저장된다.

3. Social Relationship Compute

• Encounter table에 저장된 encounter vector들을 통해 Social Relationship을 계산할 수 있다.
• Social Relationship는 frequency, freshness 두 metric이 사용된다. 얼마나 자주 만났는지, 얼마나 최근에 만났는지를 나타낸다.
• $R_i(j) = \displaystyle\sum_{k=1}^{n} F(t_b-t_j)$
• $R_i(j)$는 node $i$의 Social Relationship이다.
• $t_b$는 현재 시간, $t_j$는 node $j$를 만난 시간이다.
• 함수 $F(x)$는 가중치 함수이며, frequency와 freshness 중 어느 것에 중점을 둘 것인지 정한다.

4. Social-Tie Table Exchange

• 각 node는 encounter가 발생하면 social-tie table을 교환한다.
• 다른 node로부터 social-tie table을 수신하면 local social-tie table을 수정한다.

5. Centrality Compute

• Social-tie table을 기반으로 각 node의 centrality를 계산할 수 있다. 식은 다음과 같다.
• $C_i = \alpha \frac{\sum_{k=1}^{N} R_i(k)}{N} + (1-\alpha) \frac{(\sum_{k=1}^{N} R_i(k))^2}{N (\sum_{k=1}^{N} R_i(k))^2}$
• $\alpha$는 특정 시나리오에 따라 사용자가 결정하는 매개변수이다.
• 만약 sparse network라면 $\alpha$값을 낮춰 분포에 중점을 두고 dense network라면 높여서 평균에 중점을 둔다.

6. Node Clustering

• 계산한 Centrality를 바탕으로 k-means clustering을 통해 계층을 나눠서 각 node를 분류한다.

---

Content Request

Content requester가 특정 content를 요청하려는 경우 자신의 node id와 content name을 포함하는 Interest packet을 생성한다. 이 packet은 naive flooding을 피하기 위해(network overhead를 줄이기 위해) 높은 계층의 node에게만 forward한다.

자신과 비슷한 또는 낮은 계층의 node는 자신보다 적은 node를 만났다는 의미이다. 따라서, 자신보다 다른 node에 대한 정보가 적다는 것을 의미하기 때문에 더 높은 계층의 node에게만 Interest packet을 forward한다.

Interest packet을 받은 node는 local digest table을 통해 sender가 찾는 content name이 있는지 확인한다. 만약 일치하는 content 없다면 계속 높은 계층으로 forward된다. 만약 있다면, content provider의 node id를 interest packet에 포함하고 content provider보다 높은 계층의 node에게 interest packet을 forward한다.

Interest packet이 receiver(content provider)에게 도달하면 content provider는 content requester에게 data packet을 전송한다. 이때, forward방식은 request 방식과 동일하다. content requester보다 높은 계층의 node에게 data packet을 forward한다.

이때, content provider는 같은 interest packet에 대해 오직 한번만 response를 보낸다.

출처
You Lu, Xiao Li, et al. (2014). Information-centric delay-tolerant mobile ad-hoc networks. IEEE