網路的基礎設施經常在災難中被破壞，且需要相當長的時間來進行修復。然而在公共安全網路中，對於救難團隊而言依賴群組通訊來進行救災行動式非常重要的。第三代夥伴計畫(3GPP)在第十二個版本中定義的鄰近服務，使在公共安全網路中的使用者可進行直接的通訊。在鄰近服務的幫助下，群組通訊可以在沒有基地台的情況下使用與擴增。在這篇論文中我們主要探討如何降低鄰近服務在群組通訊中所造成的成本。當我們只考慮無法連線的成員都在一次傳輸即可與有網路連線的成員進行通訊，如何降低鄰近服務成本即相當於是一個可被貪婪演算法解決的資料源選擇問題。然而，為了傳送資料給所有的成員，我們假設需要進行k次的鄰近服務傳送。此時貪婪演算法會造成不必要的鄰近服務成本。因此本論文提出了一個遞迴的演算法來解決這樣的問題。與傳統根據可收到的傳輸距離由近而遠的選擇資料源方法不同，我們選擇由遠而近並且以可以降低鄰近服務傳輸成本的方式將無法連線的群組成員分為k個部分。根據這個分類方法，我們也可以得知在每一次鄰近服務傳輸中作為資料源和接收者的使用者。

The network infrastructures are often destroyed after disasters and it needs to take a long time to be recovered. However, the support of group communications for disaster rescue crew is important in LTE public safety networks. 3GPP Release 12 defines proximity service (ProSe) to allow direct communications for public safety within users. With the aid of ProSe, group communications can be extended without base station. This thesis studies the problem of minimizing the incurred ProSe cost for group communications. In particular, minimization of the ProSe cost for only one-round disconnected group members is equivalent to a source selection problem, which can be solved by greedy algorithm. However, to broadcast packets for all distributed group members, the number of required ProSe round of propagations increases, says k. Simply applying greedy algorithm for k rounds iteratively may cause unnecessary ProSe cost. This thesis proposes a recursive-based algorithm to address the above issue. Instead of the traditional way to determine the set of source nodes from the nearest to the farthest hop, we partition the disconnected group members into k sets by considering the total ProSe cost incurred can be reduced under this settings. Specifically, the partition is determined recursively according to the receiving sequence of packet from the farthest to nearest order. Based on the given partition, we can obtain the sets of source nodes and receivers at each round.

[1] 3GPP, “3rd Generation Partnership Project; Technical Specification Group Services
and System Aspects; Multimedia Broadcast/Multicast Service (MBMS); Stage 1
(Release 13),” TS22.146 V13.0.0, Dec. 2015.
[2] 3GPP, “3rd Generation Partnership Project; Technical Specification Group Services
and System Aspects; Multimedia Broadcast/Multicast Service (MBMS) user
services; Stage 1 (Release 13),” TS22.246 V13.0.0, Dec. 2015.
[3] 3GPP, “3rd Generation Partnership Project; Technical Specification Group Services
and System Aspects; Multimedia Broadcast/Multicast Service (MBMS); Architecture
and functional description (Release 13),” TS23.246 V13.3.0, Dec. 2015.
[4] 3GPP, “3rd Generation Partnership Project; Technical Specification Group Services
and System Aspects; Proximity-based services (ProSe); Stage 2 (Release 13),”
TS23.303 V13.2.0, Dec. 2015.
[5] 3GPP, “3rd Generation Partnership Project; Technical Specification Group Services
and System Aspects; Feasibility study for Proximity Services (ProSe) (Release 12)
,” TS22.803 V12.2.0, Jun. 2013.
[6] 3GPP, “3rd Generation Partnership Project; Technical Specification Group Services
and System Aspects; Study on architecture enhancements to support Proximitybased
Services (ProSe) (Release 12),” TR23.703 V12.0.0, Feb. 2014.
[7] 3GPP, “3rd Generation Partnership Project; Technical Specification Group Services
and System Aspects; Group Communication System Enablers for LTE
(GCSE_LTE) (Release 13),” TR22.468 V13.0.0, Dec. 2014.
[8] J. Wu et al., “On Calculating Power-Aware Connected Dominating Sets for Efficient
Routing in Ad Hoc Wireless Networks,” Journal of communications and networks,
vol. 4, no. 1, pp. 59-70, Mar., 2002
[9] 王珊晦、李明儒、蘇淑茵、李彥文, “利用D2D 提升LTE E-MBMS 之傳輸效率,”
The 20th Mobile Computing Workshop, Nantou, Aug. 2015.
[10] T. Doumi et al., “LTE for public safety networks,” IEEE Commun. Mag., vol. 51,
no. 2, pp. 106-112, Feb., 2013.
[11] X. Lin et al., “Modeling, Analysis, and Optimization of Multicast Device-to-Device
Transmissions,” IEEE Trans. Wireless Commun., vol. 13, no. 8, pp. 4346-4359,
Aug., 2014.
[12] K. Doppler et al., “Device-to-device communication as an underlay to LTEadvanced
networks,” IEEE Commun. Mag., vol. 47, no. 12, pp. 42-49, Dec., 2009
[13] Y. J. Chuang, and K. C. J. Lin, “Cellular traffic offloading through communitybased
opportunistic dissemination,” IEEE Wireless Communications and Networking
Conf. (WCNC), Shanghai, 2012, pp. 3188-3193.
[14] J. Wang et al., “Multi-phase Device-to-Device relay algorithms for data dissemination
in a cluster,” The 21st Int. Conf. on Telecommunications (ICT), Lisbon,
2014, pp. 201-205.
[15] L. Militano et al., “When D2D communication improves group oriented services
in beyond 4G networks,” Wireless Networks, vol. 21, no. 4, pp. 1363-1377, May.,
2015.
[16] X. Lin et al., “An Overview of 3GPP Device-to-Device Proximity Services,” IEEE
Commun. Mag., vol. 52, no. 4, pp. 40-48, Apr., 2014
[17] S. Yasukawa et al., “D2D Communications in LTE-Advanced Release 12,” NTT
DOCOMO Technical Journal, vol. 17, no. 2, pp. 56-64, Oct., 2015
[18] S. K. Kasera et al., “Scalable reliable multicast using multiple multicast channels,”
IEEE/ACM Trans. Netw., vol. 8, no. 3, pp. 294-310, Jun., 2000.
[19] J. F. Monserrat et al., “Joint Delivery of Unicast and E-MBMS Services in LTE
Networks,” IEEE Trans. Broadcast., vol. 58, no. 2, pp. 157–167, Jun., 2012.
[20] M.E.J. Newman and G. T. Barkema, “Monte Carlo Methods in Statistical
Physics,” vol. 13, Clarendon Press Oxford, 1999.
[21] J. Wu and H. Li, “On calculating connected dominating set for efficient routing
in ad hoc wireless networks,” in Proc. 3rd Int. Workshop on Discrete Algorithms
and Methods for Mobile Computing and Communications, ACM, New York, USA,
1999, pp. 7–14.
28