Recently, researches on various base technologies for wireless Internet services have been conducted. In the WAP (Wireless Application Protocol) Forum, a WAP gateway which does mutual conversion between existent wired Internet protocols and WAP protocols was proposed. In this paper, CSA(Client Side Agent) and SSA(Server Side Agent) for WAP gateway environments are designed and implemented, as a way of improving communication efficiency in such restrictive environments as wireless communications. Located on mobile WAP devices(CSA) and a WAP Gateway(SSA), the agents perform communication efficiency improvement activities such as a packet header reduction mechanism and a data reduction mechanism using data differencing analysis in order to reduce the size of data transmission in wireless communication environments. The Internet phone emulator of Phone.com is used in order to make sure that the implemented agents work correctly, Experimental results show that the implemented agents reduce the size of data transmission significantly.